프로그래머스 : 거스름돈 C++ (DP 사용)

programmers.co.kr/learn/courses/30/lessons/12907?language=cpp

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

 

풀이

1. 처음에 그냥 DFS 썻다가 효율성 테스트에서 시간초과 뜨더라

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

bool cmp(int a, int b)
{
    return a>b;
}

int answer = 0;

void dfs(int now,int index, vector<int> money)
{
    
    for(int i=index;i<money.size();i++)
    {
        if(now-money[i]>0)
        {
            dfs(now-money[i],i, money);
        }
        else if( now - money[i]==0)
        {
            answer++;
        }
    }
    
}


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

    sort(money.begin(),money.end(),cmp);
    
    dfs(n,0,money);
    return answer;
}

 

2. 검색해보니까 dp로 풀어야된다고 해서 다시 풀었다

 

1) 일단 젤 작은 돈만 써서 만들 수 있는 경우 기본 셋팅

2) 쓰고싶은 동전 정한 후 계산쓰

- 쫌 자세히 설명하자면

예제의 경우 1 2 5 이렇게 3개가 있다.

처음에는 1원만 쓰는 경우 계산

다음에는 1 2 원 두 종류 써서 가능한 경우 계산

마지막으로 기존 했던거에 5를 낑겨서 계산할 수 있는 방법 계산

#include <string>
#include <vector>

using namespace std;

long long dp[100001];

int solution(int n, vector<int> money) {
    int answer = 0;
    
    dp[0]=1;//0원을 만드는 경우는 1개
    
    for(int i=money[0];i<=n;i+=money[0])//젤 작은 돈만 써서 만드는 경우들 기본 셋팅
    {
        dp[i]=1;
    }
    
    for(int i=1;i<money.size();i++)//쓰고 싶은 돈
    {
        for(int j=0;j<=n;j++)
        {
            if(j>=money[i])//어차피 이 금액보다 작은놈은 못쓰니까 처리~
                dp[j] += dp[j-money[i]] % 1000000007;
            //이 동전 한개 써서 만들 수 있는 모든 경우의 수 쁠러쓰~
            //어차피 작은 값부터 순차적으로 올라가니까 이전 dp를 더하기만 하면댐
        }
    }
    answer = dp[n];
    return answer;
}