백준 9084 : 동전

코딩테스트/백준

Mev01 2022. 2. 8. 11:30

9084번: 동전

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는

www.acmicpc.net

여러 가지 종류의 동전을 이용해 금액 M을 만들 수 있는 모든 경우의 수를 구하는 문제입니다.

dp[0] = 1;
for(int i = 0 ; i < N; i++) {
    for(int j = coin[i]; j <= M; j++) {
        dp[j] += dp[j - coin[i]];
    }
}

이를 DP를 이용하려면 위와 같은 코드를 사용하면 됩니다.

오름차순으로 정렬된 코인 별로 금액 M까지 경우의 수를 각각 구해주면 됩니다.

예를 들어, (1, 2, 5)라는 동전들이 있다면

먼저 1 동전을 가지고 계산을 진행합니다.

dp[1] += dp[1 - coin[0]], dp[2] += dp[2 - coin[0]], ..., dp[M] += dp[M - coin[0]]

이렇게 하면 1~M까지 1 동전을 가지고 만들 수 있는 모든 경우의 수를 나타낼 수 있습니다.

그다음 2 동전을 이용하여 계산을 진행합니다.

j가 3일 경우, 1 동전을 이용해 1을 만드는 경우인 (1)에 2를 더해주어 (1 + 2)라는 1개의 경우의 수를 만들 수 있습니다.

따라서 dp[3] += dp[3 - coin[1]] = dp[1] = 1입니다.

아래의 블로그를 참고하면 더 자세한 설명을 볼 수 있습니다.

[백준][dp] 2293번

접근 방법 문제에 나와 있는 예시를 가지고 경우의 수를 작성해봤다. 모든 문제가 그러하긴 하지만 예시 외에도 여러 케이스를 염두해서 규칙을 생각하는 것이 필요하다! 우리가 가진 동전은 총

baejji-codingbox.tistory.com

프로그래밍나무