[프로그래머스/C++] 거스름돈

문제

문제 설명

 

풀이

 

 

처음에 DP로 풀면 되겠다 생각했다가 단순히 100종류에 100000개면 정렬만 잘 하면 빨리 통과하지 않을까 생각해서 그냥 풀었다. 그랬더니 효율성에서 시간초과가 걸려 다시 DP로 돌아왔다.

​

2차원 vector를 만들고 n원을 만드는 경우를 재귀로 구하도록 처음에 코드를 짰는데, 효율성 테스트 중 하나를 자꾸 통과하지 못했다. 그래서 1차원 vector로 바꿔서 다시 풀었더니 통과할 수 있었다.

​

1차원 vector로 푸는 방법은 처음에 동전 하나를 사용해서 만들 수 있는 n보다 작은 모든 거스름 돈의 수를 구한다.

그리고 그 거스름 돈의 자리에 1을 저장한다.

 

이후 두번째 동전도 사용해 거스름 돈을 주는 수를 구한다.

두번째 동전을 a라고 하면, k가 0부터 n까지 증가하도록 하고

k원을 구하는 방법은 DP[k]=DP[k]+DP[k-a]로 누적시켜서 구하면 된다.

 

이렇게 하면 단순히 100*100000의 시간복잡도로 거스름 돈의 경우의 수를 구할 수 있다.

 

[예시] 누적시켜서 구할 수 있는 이유를 a가 2일때로 한번 알아보자.

 

DP[2]=DP[2]+DP[2-2] 를 구한다음

DP[4]=DP[4]+DP[2]를 구하면 이제 2원짜리 동전을 한번 사용한 경우가 이전의 DP[2]를 구할 때, 누적되어 있다.

 

그래서 DP[4]에서 계산하는 DP[2]에 2원짜리 동전을 하나 사용하는 DP[2]+DP[0]의 경우가 포함되어 있어서 단순히 돈의 가치인 a를 순차적으로 빼면서 계산을 해도 답을 구할 수 있게 된다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> money) {
    int answer = 0;
    vector<int> DP(n+1,0);
    for (int i=0; i<=n/money[0]; i++)// 초기화
    {
        DP[i*money[0]]=1;
    }
    for (int i=1; i<money.size(); i++)
    {
        for (int j=0; j<=n; j++)
        {
            if (j-money[i]>=0)
            {
                DP[j]=DP[j]+DP[j-money[i]];
            }
        }
    }
    return DP[n];
}

 

---

 

1차원 배열을 2개 사용해서 고쳐볼까 생각했는데, 다른 사람이 푼 풀이 중 더 좋은 아이디어가 있어서 참고를 했다.

이번 문제는 처음에 쉽다고 생각했는데, 생각보다 효율성 통과 때문에 어려웠던 문제였다...

 

프로그래머스