https://www.acmicpc.net/problem/2293
2293번: 동전 1첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.www.acmicpc.net
처음에 ㅈ밥으로생각했는데, 예상외로 어려웠다.
먼져 동전을 저장하고, dp배열을 생성한다.
여기서 내가 이해가 안됬던 부분은, 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 라는 문장이다
예로 동전이 1,2 가 있다면,
3을만들수 있는 경우는 1+1+1 , 1+2, 2+1 ,3 총 4가지이다.
여기서 중복되는 1+2,2+1중 하나를 제거하면 3가지가 나와야 한다.
정답을 찾아봤는데, 이걸 어떻게 제거하는지 이해가 되지 않았다.
답은 coin과 dp 2중 반복으로 만들어서 해결한다.
앞서예시 3 (1,2)를 예로 들자면,
먼져 coin의 1만 사용해서 만들 수 있는 경우를 구한다.
1만으로 3까지의 숫자를 만드는 경우는 1+1+1 하나밖에 없다. [1,1,1,1]
다음에는 2로 만드는 경우이다.
2로 2를 만드는 경우의 수는 1이고, 3을 만드는 경우의 수는 1+2 1이다.
그러므로 배열은 [1,1,2,2]가 된다.
이 경우에, 1은 생각하지 않으므로, 2+1의 경우는 아예 계산을 하지 않게 되고, 1+2의 경우만 계산이 된다.
참고로, dp[0]이 1인 이유는, 동전으로 dp[동전] 을 만드는 경우의 수는 항상 1이므로, 이를 계산하기 위해서이다.
다음에 다시 풀어봐야겠다.
import sysinput=sys.stdin.readlinen,k=map(int,input().split()) #동전수 #목표
coins=[int(input())for _ in range(n)] #동전dp=[0 for _ in range(k+1)]
dp[0]=1 #coin에 해당하는 값에 1을 더해줄 용도for coin in coins: for i in range(1,len(dp)):
if i-coin>=0: dp[i]+=dp[i-coin]print(dp[k])