백준 2293번 : 동전 1

 

 

 

👉 제출 코드

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
c = [int(input()) for i in range(n)]

dp = [0 for i in range(k+1)]
dp[0] = 1

for i in c:
    for j in range(i, k+1):
        if j-i >= 0:
            dp[j] += dp[j-i]

print(dp[k])

 

핵심뽀인뜨 : 

* 동적 계획법 (Dynamic Programming, DP) 문제를 풀 때 고려해야할 것들 

• '전체 문제'를 '부분 문제'로 잘 나눠서 문제를 접근했는가?
• 전체 문제를 해결하기 위한 부분 문제의 점화식은 무엇인가?
• 부분 문제들을 해결 후 얻은 결과값들을 메모이제이션하였는가?
• 부분 문제의 점화식은 부분 문제들 사이의 '관계'를 빠짐없이 고려했는가?

 

문제를 통해서 알 수 있는 점 : 

* 앞서 살펴본 동적 계획법 고려사항들을 바탕으로 문제를 바라봐보자!

• '전체 문제'를 '부분 문제'로 잘 나눠서 문제를 접근했는가?
  • 전체 문제 : 가치의 합이 k원이 되는 경우의 수
  • 부분 문제 : 가치의 합이 i (1 ≤ i ≤ k)원이 되는 경우의 수 
    • (부분 문제를 더 세부적으로 나눠보자면) 특정 동전을 썼을 때 가치의 합이 i원이 되는 경우의 수 
• 전체 문제를 해결하기 위한 부분 문제의 점화식은 무엇인가?
• 부분 문제들을 해결 후 얻은 결과값들을 메모이제이션하였는가?
  • 앞서 언급한 부분 문제들을 해결해나가며 메모이제이션 할 것인데, 시간 제한이 0.5초이며 메모리 제한도 4MB밖에 되지 않기 때문에 하나의 리스트 안에서 덮어 씌우는 식으로 빠르게 해결해나가야 함
• 부분 문제의 점화식은 부분 문제들 사이의 '관계'를 빠짐없이 고려했는가?
  • 입출력 예시로 주어진 경우 말고도 다른 예시를 생각해보며 테스팅해봐야 할 듯함 

 

필요한 입력값 :

 

 

출력값:

 

 

 

👉 파악한 것을 바탕으로 코드를 작성해보자!

 

 

 

👉 알면 좋은 코드들

📍동적 계획법 문제를 풀 때 꿀팁이 없을까? 하고 구글링을 엄청 했었는데, 그 중에서 제일 깔끔하게 정리가 잘 되어 있던 블로그였음! 

(참고) https://mong9data.tistory.com/68