tlov
2294번 문제 메모 본문
참고: 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
동전 n가지를 무한히 쓸 수 있다? == dp를 왼쪽부터 누적
동전 n가지를 1개만 쓸 수 있다? == dp를 오른쪽부터 누적.
0 1 2 3 4 5 6 7 8
1원으로 얘네들을 만든다.
1 2 3 4 5 6 7 8개가 필요.
2원으로 만든다.
테이블로 표현하자.
dp | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
1원 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
2원 | 0 | 1 | 1 | 2 | ... |
빨간 글씨부터 갱신이 되는 부분이다. 즉, 점화식이 min(dp[i], dp[i-2] + 1);이다.
번외) n가지를 1개만 쓸 수 있다면?
for (int i = 0; i < n; i++) {
int tmp = Integer.parseInt(br.readLine());
for (int j = k; j >= tmp; j--) {
dp[j] = Math.min(dp[j], dp[j - tmp] + 1);
}
}
1, 2, 5로 5원을 만든다고 하면 테이블이 다음처럼 이루어진다.
dp | 0 | 1 | 2 | 3 | 4 | 5 |
1원 | 0 | 1 | inf | inf | inf | inf |
2원 | 0 | 1 | 1 | 2 | inf | inf |
5원 | 0 | 1 | 1 | 2 | inf | 1 |
흐름을 따라가면 모두 1개만 사용해서 k원을 만드는 것을 볼 수 있다. 근데 흐름을 따라가면 이렇게 나오는건 알겠는데, 왜 이렇게 되는건지는 아직 잘 모르겠다.
'알고리즘 문제' 카테고리의 다른 글
1513 문제에서 왜 4차원 배열을 사용해야 하나? (0) | 2024.09.25 |
---|---|
2293 - 동전 1 (0) | 2024.09.23 |
2240 - 자두나무 (0) | 2024.09.20 |
2098 - 외판원 순회 (2) | 2024.09.17 |
2565 - 전깃줄 (0) | 2024.09.12 |