[코딩 테스트 연습(파이썬/Python)] 백준 2293번 _ 동전 1

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

2293번: 동전 1

[문제]

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

[입력]

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

[출력]

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

 

[아이디어]

1) 동전 순으로 합이 1,2,3, ..., k원을 만드는 방법의 수를 모두 구하여 누적으로 쌓는다.

2) 0번째의 인덱스을 1로 설정해 동전 1개로 n원을 만드는 방법 1가지를 만들어낸다.

 

a,b = map(int, input().split())
n=[int(input()) for _ in range(a)]
dp = [1] + [0]*b
for i in n:
    for j in range(i,b+1):
        if j-i >=0:
            dp[j] += dp[j-i]
print(dp[-1])

DP에서 심하게 벽을 느끼는 중이다,, 다른 사람 풀이를 참고해 이해했다. dp 문제는 결국 subproblem을 어떻게 설정하고 목표에 도달하느냐인데, 아직 하위 문제 설정이 상황 별로 능숙하게 되지 않는다. 이번엔 변수 1개로 해결해야한다는 것 정도는 알았는데, 그리고 비슷하게 접근도 했던 것 같은데 결국 꼬여서 해결하지 못했다. 내가 놓쳤던 핵심은 dp의 인덱스로 for문을 먼저 돌리는 것이 아니라, 각 동전에 대해 for문이 먼저 돌아가게 하는 것이었다. (dp의 인덱스를 상위 for문으로 돌리게 되면, 문제에서 원하지 않는 중복이 발생한다.)