(파이썬 python) 백준 2293번 : 동전 1

# 2293번 : 동전1

n,k = map(int,input().split())

coins=[]
for _ in range(n):
    coins.append(int(input()))

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

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

동적계획법(Dynamic Programming)알고리즘을 풀 때에는 항상 아래의 내용을 확인하면서 풀어야 한다.

• 중복되는 서브문제(overlapping subproblem) : 큰 문제를 작은 문제로 쪼갤 수 있어야한다. 즉 전체의 문제를 같은 방법이지만 부분문제로 나누어야 하며 이를 통해 나오는 부분문제의 점화식을 구할 수 있어야 한다.
• 최적 부분 구조(optimal substructure) : 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다. 
• 메모이제이션 or 재귀식 : 알고리즘 구현할 때 메모이제이션 또는 재귀방법을 통해서 구현하였는가?

위의 문제는 1,2,5 이 세개의 동전조합으로 10원을 만드는 경우의 수를 찾는 것이다.

전체 문제를 부분문제로 쪼개기 위해서는 사용가능한 동전 조합에서 1원을 만드는 경우의 수, 2원 경우의 수 , 3원 경우의 수.... 10원 경우의 수 이렇게 생각하면서 규칙을 찾아야 한다.

 

cf. dp[0] = 1인 이유는 0원을 만드는 경우의 수가 1개라는 의미가 아니라 나중에 dp[1]을 구할 때 사용하려고 선언한 것 뿐이다. 착각하지 말자

 

먼저 1원만으로 만들 수 있는 경우의 수를 구한다.

dp[1] = 1 (1)

dp[2] = 1 (1+1)

dp[3] = 1 (1+1+1)

...

dp[10] = 1

 

이제 그 다음으로 1,2원으로 만들 수 있는 경우의 수를 구한다.

dp[1] = 1 

=> 그대로 1개의 경우의 수 밖에 없다. 

 

dp[2] = 2 (1+1, 2) 

=> 1원만으로 만든 dp[2]에 경우의 수 하나가 추가되었다. 즉 업데이트전dp[2] + dp[0] 이다. dp[3], dp[4]까지 확인해보자.

 

dp[3] = 2 (1+1+1, 1+2) 

=> 1원만으로 만든 dp[3]의 경우의 수에 dp[1]에 2를 더한 경우의 수 하나가 더해진것이다. 즉 업데이트전dp[3] + dp[1]

 

dp[4] = 3 (1+1+1+1, 1+1+2, 2+2)

=> 업데이트 전 dp[4](1+1+1+1) 에 dp[2] (1+1, 2) 에 2를 더한 경우의 수 2개를 더한값이다.

...

 

점화식이 dp[i] += dp[i-coins]가 된다는 것을 추론할 수 있다.

 

DP는 점화식을 잘 세우는 것이 중요하다!! 결국 점화식만 잘 세우면 끝난다

 

 

 

참고 블로그

https://mong9data.tistory.com/68

https://seongonion.tistory.com/108