[PS] 2293) 동전 1

https://www.acmicpc.net/problem/2293

2293번: 동전 1

Gold5) 2293.동전 1

 

• 다이나믹 프로그래밍

다이나믹 프로그래밍 풀이가 계속 감이 잡히지 않아 아예 다이나믹 프로그래밍 카테고리에 들어가서 문제들을 풀었다. 골드5지만 다이나믹 프로그래밍은 난이도 체감이 천차만별이다. 기본적인 동전 문제 구성에 애초에 카테고리로 들어간 문제라 처음부터 DP로 접근했다. 사실 문제를 낯선 상황에서 만난다면 DP를 떠올리는 것부터가 문제이다. DP를 생각하고 접근했음에도 꽤나 고전했다.

 

문제의 구성은 다음과 같다. 주어진 동전을 통해 주어진 값을 맞추는 동전 조합의 개수를 구하는 문제다. 쉽게 말해 10원, 100원 500원 동전을 제한 없이 사용할 수 있고, 1000원을 맞추는 조합의 개수를 세는 것이다. 뭐 쉽게 생각해보면  10원 100개, 100원 10개, 500원 2개 등 1000원을 맞추는 방법은 여러가지가 있을 것이다. 이 경우의 수를 모두 세는 것이다. 우선 dp배열을 어떻게 구성할 지 생각해봤는데, 일차원 배열로 dp[i]는 i번째까지 경우의 수를 저장하도록 했다. 이후 점화식은 주어진 동전을 통해 끌어냈다. 예를 들어, 1, 3, 5동전이 있고 10원을 맞춘다고 할 때, dp[10]은 dp[10-1] 또는 dp[10-3] 또는 dp[10-5]에서 답을 도출할 수 있다고 판단했다. 서로 관계를 가질 항을 유추하고 실제로 점화식을 끌어냈다. 우선 문제에 주어진 예제로 dp[0]부터 1원씩 증가시키며 규칙을 찾았다. 1, 3, 5 동전을 그대로 다시 사용해서 유추해보면 dp[10-1] 즉 dp[9]는 9원을 만들 수 있는 경우의 수이다. 이 때, 1원 동전을 가지고 있으므로 dp[10]은 dp[9]의 경우의 수에 1을 추가하여 그 경우의 수를 그대로 가져올 수 있다. 따라서 dp[10] += dp[9]만큼 경우의 수를 추가할 수 있다. 이는 나머지 동전 경우에도 마찬가지이다.

 

로직을 그대로 코드로 옮기면 생각보다 간단하다.

dp = list(0 for _ in range(k+1))
    for c in board :
        if k<c :
            continue
        dp[c] += 1
        for i in range(k+1) :
        	if 0<=i-c :
            	dp[i] += dp[i-c]
    print(dp[k])

c는 문제에서 주어진 각 동전의 값을 나타낸다. 각 동전에 해당하는 값은 그 동전 자체로 맞출 수 있으므로 dp[c]+=1구문이 있다. 그 밑의 for문은 위의 로직처럼 가진 동전만큼 이전의 경우의 수를 가져오도록 계속 초기화해준다.

 

DP는 점화식을 이끌어내도, 또는 정답을 보더라도 잘 이해가 되지 않을 수 있다. 많은 연습이 필요하며 적은 수의 예시를 들어가며 규칙을 몸으로 와닿게 하는 것도 좋은 방법이다.