2293

날짜 : 2023. 05. 05

사용 언어 : python

 

문제

 

 

코드

import sys

n, k = map(int, sys.stdin.readline().split())  # 동전 종류, 가치의 합
dp = [0] * (k+1)
dp[0] = 1
coin = list()
for _ in range(n): coin.append(int(sys.stdin.readline()))
coin.sort()  # 동전 정렬
for i in range(n):  # 각 동전에 대하여 체크
    if i == 0:
        for j in range(coin[0], len(dp), coin[0]):
            dp[j] = 1
    else:
        for j in range(coin[i], len(dp)):
            dp[j] += dp[j - coin[i]]
    #print(dp)
#print(dp)
print(dp[-1])

 

 

풀이

예제를 기준으로 했을 때의 케이스

- 목표값(K)이 10, 입력받은 동전이 (1, 2, 5)인 케이스로 진행한다.

- 먼저 오름차순으로 정렬 후 첫번째 동전에 대하여 dp값을 1로 체크한다.(동전 1로 만들 수 있는 케이스 가산)

- 이후 동전 1, 2로 만들 수 있는 케이스를 하나하나 만들어서 체크한다.

- 이 경우, 동전 2일 때 표의 최신화는 dp값이 2일때부터 이루어지며, 다음과 같은 규칙이 발생한다.

dp[i] = dp[i] + dp[i - 최신화가 이루어지는 동전값]

- 이를 반복하여 갱신한 후 dp[k]를 출력한다.

- 다만 dp[0]은 처음에 초기화할 수 없기 때문에 반복문 이전에 dp[0] = 1로 초기화한다.

 

알게된 점

- 맨 처음 하나씩 케이스를 체크해가면서 문제를 푸는 과정에서 dp[i] = dp[a] + dp[b] 형식으로 전개하는 것으로 생각했다.

- 그렇지만 중복이 발생해서 이를 어떻게 처리할지 막막했고, 다른 풀이를 체크했다.

- 확실히 풀이는 되게 간단한데 규칙성을 발견하는데 많은 노력이 필요해보인다.

 

 

참고 사이트

- https://velog.io/@jxlhe46/백준-2293번.-동전-1-bfi120m5

[백준] 2293번. 동전 1