백준 9084. 동전

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

9084번: 동전

 

dp 문제.

예전에 프로그래머스에서 같은 문제를 풀었던것 같다.

 

d[i][j] : j번째 이상 동전으로 i원을 만들수 있는 방법의 수 

 

예를들어 동전이 {1,2,4,5} 원 짜리가 있으면, 

d[10][0]은 0번째 동전인 1원짜리 이상인 동전들 즉 {1,2,4,5}원들로 10원을 만들수 있는 방법의 수.

d[10][2]은 2번째 동전인 4원짜리 이상인 동전들 즉 {4,5}원들로 10원을 만들수 있는 방법의 수.

 

이 문제의 핵심은 d[i][j]를 정의하는 것이다.

만약 d[i][j]를 j번째 동전을 포함해 i원을 만들수 있는 방법의 수로 정의한다면 중복되는 경우가 생겨버린다.

하지만 d[i][j]를 j번째 이상 동전으로 i원을 만들수 있는 방법의 수로 정의한다면 중복이 생기지 않는다. 

 

점화식은 d[i][j] = d[i-j번째 동전][j] + d[i-j번째 동전][j+1] + ... + d[i-j번째 동전][N-1]

 

 

 

---

https://tose33.tistory.com/569

백준 2293. 동전 1

 

위 글에서 처럼 1차원 배열을 사용하는 방법도 있다.