본문 바로가기
Algorithm/프로그래머스

[프로그래머스]연습문제 : 거스름돈 (level 3)(c++)

by HBGB 2020. 7. 1.

https://programmers.co.kr/learn/courses/30/lessons/12907

 

코딩테스트 연습 - 거스름돈

Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5��

programmers.co.kr

 

 

#include <string>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int solution(int n, vector<int> coins) {

    // 동전으로 N원을 만드는 방법의 수
    vector<int> ways(n + 1);

    // 0원을 만드는 방법의 수 : 1 (아무동전도 사용하지 않는 것)
    ways[0] = 1;

    // [N]원을 만드는 방법의 수 += [N - x]원을 만드는 방법의 수 (x = 코인)
    for (int coin : coins)
    {
        for (int i = coin; i <= n; ++i)
        {
            ways[i] += ways[i - coin];
            ways[i] %= MOD;
        }
    }
    
    return ways[n];
}

 

 

거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때,
Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항
- n은 100,000 이하의 자연수입니다.
- 화폐 단위는 100종류 이하입니다.
- 모든 화폐는 무한하게 있다고 가정합니다.
- 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요.

(편의상 돈의 종류money를 동전 coin이라고 칭하겠습니다)

 

 

처음부터 완전탐색 선택지는 배제해야 하는 문제이다. 

경우의 수를 구하는 문제인데, 문제에서 명시적으로

"정답이 커질 수 있으니 1,000,000,007로 나눈 나머지를 리턴하라"고 되어있기 때문이다.

 

 

따라서 이문제는 DP로 풀어야 하는데, 이때 동전을 더해주는 순서가 중요하다.

 

예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면
다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.

1원을 5개 사용해서 거슬러 준다.
1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
5원을 1개 사용해서 거슬러 준다.

 

문제에서 주어진 예시를 활용할 때, 동전 더해주는 순서를 명확히 하지 않으면

D[3] 111, 12, 21 이렇게 총 3가지가 되어버린다. (2가지가 되어야 한다)

 

 

그렇다면 점화식을 만들때 방향성이 다음과 같다.

1. 돈의 단위를 차차 늘려간다.

2. 동전의 단위도 차차 늘려간다.

 

결국 점화식은 다음과 같이 완성할 수 있다.

D[m] = sum(D[m - coin_x]) (이때, 1 ≤ m ≤ Ncoin_x는 문제에서 주어진 동전의 단위)

당연히 m - coin_x ≥ 0 이어야 한다.

더보기

N원을 만드는 방법의 수

= N - coin_1 원을 만드는 방법의 수 (coin_1 코인을 이용할 때)

+ N - coin_2  원을 만드는 방법의 수 (coin_2 코인을 이용할 때)

+ N - coin_3  원을 만드는 방법의 수 (coin_3 코인을 이용할 때)

...

가 된다.

 

이해를 돕기 위해 예시를 쭉 써보면,

coin = 1일때,

D[1] += D[0]  (= 1)

D[2] += D[1]  (= 1)

D[3] += D[2]  (= 1)

D[4] += D[3]  (= 1)

D[5] += D[4]  (= 1)

 

coin = 2일때,

D[2] += D[0]  (= 2)

D[3] += D[1]  (= 2)

D[4] += D[2]  (= 3)

D[5] += D[3]  (= 3)

 

coin = 5일때,

D[5] += D[5]  (= 4)

 

 

이를 코드로 나타내면 다음과 같다.

// [N]원을 만드는 방법의 수 += [N - x]원을 만드는 방법의 수 (x = 코인)
for (int coin : coins)
{
    for (int i = coin; i <= n; ++i)
    {
        ways[i] += ways[i - coin];
    }
}

 

 

댓글