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

 

첫 번째 접근 (시간초과)

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

long long dp[100002][102];

void init(vector<int> money) {
    for(int i=0; i<=money.size(); i++) {
        int tmp = money[i];
        dp[tmp][i] = 1;
    }
    
}

int solution(int n, vector<int> money) {
    int answer = 0;
    init(money);
    
    for(int i=1; i<=n; i++) {
        for(int j=0; j<money.size(); j++) {
            for(int k=0; k<=j; k++) {
                if(i - money[j] <= 0) continue;
                dp[i][j] = (dp[i][j] + dp[i - money[j]][k]) % 1000000007;
            }
        }
    }
    
    for(int i=0; i<money.size(); i++) {
        answer = (answer + dp[n][i]) % 1000000007;
    }
    
    return answer;
}

 

 

시간초과가 발생한 첫 번째 접근입니다.

 

최악의 경우 O(100 * 100 * n) 으로 10억이 나오기 때문에 효율성 테스트를 모두 통과하지 못했습니다.

 

 

두 번째 접근 (정답 코드)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

long long dp[100002];

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

 

 

위 방식대로 하게되면 첫 번째 접근과 똑같은 결과를 보장하며 * 100 을 떼어낼 수 있습니다.

 

어차피 뒤에 큰 수를 붙이는 것이기 때문에 2차원 배열을 만들지 않고 1차원 배열을 만들어 해결했습니다.