[코딩테스트 C++] 거스름돈

오늘의 문제

거스름돈

나의 풀이

#include <string>
#include <vector>
#include <algorithm>
#define MOD 1000000007;

using namespace std;

int solution(int n, vector<int> money) {
    
    vector<int> dp(n+1, 0);
    dp[0] = 1;
    for(int i=0;i<money.size();i++){
        for(int j= money[i];j<=n;j++){
            dp[j] += dp[j-money[i]];
        }
    }
    return dp[n];
}

모범 답안

배울 점

• 참고해서 풀게 되었다.
• 어제 풀었던 문제와 같은데, 나뉘어지니 생각이 정리가 안되더라 DP인것은 딱 알았는데,,
• DP의 핵심은 이전까지 잘 되어있다가 이번 차례를 생각하는것인데 그 차례에서 각 연산을 수행하려니 아 이전에 수행했던 것과 겹치면 똑같다는 생각에 문제를 풀지 못했음. 이건 순열이 아니라 조합이라, 순열이라면 2가 먼저나오고 1이 나오는거랑 1이 먼저나오고 2가 나오는거랑 다르니.
• 그때부터 dfs로 풀어볼까 하고 풀었더니 효율성에서 시간초과가 났다. 당연한것이 n이 100000이하 자연수인데 dfs로 모든 조합을 구해버리면 큰일난다.
• 와 이걸 어쩐담 하고 결국 힌트를 보게 되었더니 이거였다.
• 처음에 했던것처럼 실행하면 이전에 다른 연산이 수행된 결과가 반영되는데, 각 연산마다 DP를 돌리면 반영이 되지않는다. 그냥 차례대로 더해진다. 이걸보고 아직 한참 멀었다 싶었다..