[BOJ] Python 백준 2294번 동전 2 골드 4

한동안 알고리즘 문제 풀이에 신경을 쓰지 못하여 부족한 DP에 대한 감을 잡으려고 고른 문제다.

 

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

2294번: 동전 2

 

DP 문제는 구현 자체가 어렵진 않지만 문제 해결법에 접근하는 과정이 다소 어려운 것 같다.

 

다른 알고리즘 같은 경우는 연습을 통해 익숙해진다면 DP는 아무리 연습해도 문제에 따라 쉽게 떠오르지 않는 알고리즘 같다.

 

문제 풀이

---

해당 문제의 소재는 다소 익숙한 원하는 금액을 지불하는 동전의 최소 개수다.

 

동전의 개수는 n개이고 가치의 합은 k이며 각각 1 <=n <=100, 1 <=k <=10000의 제한 조건을 갖는다.

 

같은 동전이 여러 번 주어질 수 있지만 가치의 합인 k를 dp 리스트로 잡고 각 인덱스마다 n번 반복하면 되므로 시간 복잡도는 O(n*k), 즉 최대 100만 번이라 딱히 고려하진 않아도 되는 조건이었다.

 

물론 필자는 효율성을 높이기 위해 Set로 형 변환했다가 다시 List로 형 변환했었다.

 

이렇게 Set로 형 변환하면 중복된 원소를 제거할 수 있다.

 

다만 이 문제에서 중요하게 고려해야 할 점은 가치의 합인 k로 만드는 것이 불가능할 수도 있단 점이다.

 

여태 경험했었던 동전 DP 문제는 애초에 불가능에 대한 조건은 없었기에 최소 개수만 구하는데 집중했었고 이번 문제도 처음에 똑같이 시도했다가 틀렸단 메시지를 받았다.

 

그 과정에서 문제를 다시 정확히 읽고 스스로 테스트 케이스를 만들어 오류를 잡아내는 연습도 필요한 것 같다.

 

각설하고 전체 코드를 통해 설명하도록 하겠다.

 

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

coin=list(set(coin))
dp=[0 for i in range(k+1)]
for i in range(1,len(dp)):
    for j in range(len(coin)):
        if i-coin[j]==0:
            dp[i]=dp[i-coin[j]]+1
        elif i-coin[j]>0 and dp[i-coin[j]]!=0:
            if dp[i]==0:
                dp[i]=dp[i-coin[j]]+1
            elif dp[i-coin[j]]+1<dp[i]:
                dp[i]=dp[i-coin[j]]+1

if dp[k]==0:
    print(-1)
else:
    print(dp[k])

 

1번째 줄은 n과 k를 입력받고 2번째 줄의 coin은 동전의 가치를 입력받을 리스트다.

 

6번째 줄이 중복을 제거하는 코드이며 7번째 줄의 dp는 k인 가치의 합을 인덱스로 갖는 dp 리스트다.

 

어떤 것을 dp 리스트로 잡을지는 문제를 많이 풀다 보면 감 잡게 될 것이다.

 

이제 8번째 줄부터 이중 for문을 통해 전체 dp 리스트를 돌며 각 인덱스마다 coin 리스트를 반복해 해당 인덱스가 해당하는 값에서 동전을 쓸 수 있는지 확인하고 쓸 수 있다면 최소 개수인지 확인한다.

 

10번째 줄의 if 문은 동전의 가치를 현재의 가치에서 뺏을 때 0원이라면 동전을 한 개 사용할 수 있단 뜻이므로 현재 가치의 동전 개수를 업데이트했다.

 

12번째 줄의 if 문에 주목해야 하는데 현재 가치에서 동전의 가치를 뺀 값이 0보다 크고 그 뺀 값의 동전 개수가 0개보다 많을 때만 개수를 업데이트해줬다.

 

왜냐하면 만약 현재의 가치에서 동전의 가치를 뺀 가치에 대한 동전의 개수가 0개 라면 해당 가치로 동전을 조합할 수 없기 때문이다.

 

예를 들어 k가 10이고 n이 1이며 동전의 가치가 3일 때를 고려해 보자.

 

dp[10]인 상황에서 동전의 가치를 뺀 dp[7]을 생각해보면 dp[7]은 0이다.

 

3으로는 절대로 7을 만들 수 없기 때문이다.

 

따라서 7원으론 동전을 조합할 수 없기 때문에 10도 불가능하다는 얘기가 된다.

 

이 부분만 고려한다면 골드 문제를 도전하는 사람들에게 나머진 딱히 어려운 부분이 없을 것이라 생각한다.

 

결과 화면

 

이 문제를 통해 지문을 잘 읽고 테스트 케이스를 만들어보는 과정을 직접 해보는 것이 중요하다는 것을 체감했다.