1차 풀이 (2018-08-08, 메모리 초과) |
적당히 동전을 고르고, 채워야 할 나머지 가치를 부분문제로 만든다.
100원을 만들어야 하는 문제에서 40원 동전 1개를 선택했을 경우,
남은 60원은 재귀적으로 호출하여 문제를 해결한다.
답의 형태를 제한하자.
한 차례에 하나의 동전을 선택하도록 구현했다고 하자.
다음과 같이 "순서는 다르지만 실제로는 같은 경우"인 해답이 도출된다.
- 20원 → 10원 → 30원 → 20원
- 10원 → 30원 → 20원 → 20원
- 30원 → 20원 → 20원 → 10원
- ...
위처럼, 중복되는 경우도 모두 정답으로 해석하므로,
구해진 값은 정답보다 항상 크게된다.
위의 문제점을 해결하려면 답의 형태를 제한해야 한다.
다음과 같이 조건을 거는 것이다.
N번째 차례에 X원 동전을 골랐다면,
N+1번째 차례에는 X보다 작은 동전을 골라야 한다.
(한 번에 X원 동전을 여러개 고를 수 있다.)
3번답 이외에는 위의 제약을 위반하므로 답이 될 수 없다.
즉, 표준화된 대표값만을 채택하므로 중복되는 답이 없어진다.
메모이제이션으로 성능을 향상시키자.
위의 조건들을 구현하려면 solve 함수에 2가지 파라미터가 필요하다.
- 채워야 할 가치.
- 이번에 골라야 할 동전의 인덱스 넘버.
중복되는 부분문제를 다시 계산하지 않기 위해,
파라미터의 조합을 인덱스로 한 메모이제이션을 활용한다.
채워야 할 가치의 범위는 (1~10000)이고,
동전의 종류 수의 범위는 (1~100)이므로,
int cache[10001][101]의 캐싱 메모리를 두어,
이미 한번 계산된 부분문제 다시 풀어야 할 때, 캐싱된 값으로 대신한다.
2차 풀이 (2018-08-09, 2024 KB, 0 MS) |
하향식으로 풀지말고 상향식으로 풀자.
큰 문제를 풀기위해 작은 부분문제들을 푸는 것 보다, (하향식)
작은 부분문제들의 합으로 큰 문제를 도출해나가는 것도 생각해보자. (상향식)
하향식 →
4번 문제를 풀기위해 3, 2, 1 문제를 호출함.
3번 문제를 풀기위해 2, 1 문제를 호출함.
2번 문제를 풀기위해 1 문제를 호출함.
상향식 ←
1번 문제를 풀어 2, 3, 4 문제를 푸는데 사용.
2번 문제를 풀어 3, 4, 문제를 푸는데 사용.
3번 문제를 풀어 4 문제를 푸는데 사용.
DP 문제는 반드시 재귀로만 풀어야 하는 것이 아니다.
DP의 중요 포인트는 점화식.
아래에서부터 차근차근 동전을 더해나가자.
1, 2, 5원 동전이 있고 10원을 만들어야 한다고 가정하자.
먼저, 1원에 집중하자.
1원을 만드는 방법은
0원을 만드는 방법에서 1원을 더한 것.
2원을 만드는 방법은
1원을 만드는 방법에서 1원을 더한 것.
3원을 만드는 방법은
2원을 만드는 방법에서 1원을 더한 것.
k원을 만드는 방법은
k-1원을 만드는 방법에서 1원을 더한 것.
이제, 2원에 집중하자.
2원을 만드는 방법은
0원을 만드는 방법에서 2원을 더한 것.
3원을 만드는 방법은
1원을 만드는 방법에서 2원을 더한 것.
k원을 만드는 방법은
k-2원을 만드는 방법에서 2원을 더한 것.
이제, 5원에 집중하자.
5원을 만드는 방법은
0원을 만드는 방법에서 5원을 더한 것.
6원을 만드는 방법은
1원을 만드는 방법에서 5원을 더한 것.
k원을 만드는 방법은
k-5원을 만드는 방법에서 5원을 더한 것.
암묵적으로 낮은 가치의 동전을 먼저 사용하도록 되어있기 때문에,
위의 방법들은 각각 독립적이다.
따라서,
각 방법의 합이 최종적으로 k원을 만드는 방법의 합이 된다.
