[프로그래머스 Level 3] 카운트 다운 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/131129

프로그래머스

 

 

전형적인 dp 문제이다 . dp[i] = {dp[i-j]+1, dp[i-j]+(싱글 or 불이면 1)}와 같은 식이다.

i는 1부터 100,000까지이고, j는 vector v의 왼쪽 값을 뜻한다. 추가적으로 v의 오른쪽 값은 싱글 or 불인지에 대한 값이다.

 

 

#include <vector>

using namespace std;

//왼쪽이 다트 개수, 오른쪽이 (싱글,불) 개수
vector<int> dp[100001];

vector<int> solution(int target) {
    vector<int> answer;
    
    dp[0]={0,0};
    for(int i = 1 ; i<=100000; i++){
        dp[i]={987654321,987654321};
    }
    
    vector<pair<int,int>> v = {{1,1},{2,1},{3,1},{4,1},{5,1},{6,1},{7,1},{8,1},{9,1},
    {10,1},{11,1},{12,1},{13,1},{14,1},{15,1},{16,1},{17,1},{18,1},{19,1},{20,1},
    {50,1},{22,0},{24,0},{26,0},{28,0},{30,0},{32,0},{34,0},{36,0},{38,0},{40,0},
    {21,0},{27,0},{33,0},{39,0},{42,0},{45,0},{48,0},{51,0},{54,0},{57,0},{60,0}};
    
    for(int i = 0; i<=100000; i++){
        for(int j = 0 ; j<v.size(); j++){
            if(i+v[j].first>100000){
                continue;
            }
            if(dp[i+v[j].first][0]>dp[i][0]+1){
                dp[i+v[j].first][0]=dp[i][0]+1;
                dp[i+v[j].first][1]=dp[i][1]+v[j].second;
            }else if(dp[i+v[j].first][0]==dp[i][0]+1){
                if(dp[i+v[j].first][1]<dp[i][1]+v[j].second){
                    dp[i+v[j].first][1]=dp[i][1]+v[j].second;
                }
            }
        }
    }
    answer = dp[target];
    return answer;
}