[프로그래머스 Level 2] 완전범죄 (C++)

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

프로그래머스

 

 

생각 흐름

• dfs로 하면 2^40이므로 시간초과, 그리디도 생각해봤지만, 1번 예제에서부터 그리디로 하기엔 어려울 거 같았다.
• 최소값을 구해야 하는 문제여서 dp로 접근하기로 결정
• dp[info 개수] = A의 흔적 개수로 진행하려고 했는데 B의 흔적 개수에 대해 따질 수 없어서 포기
• dp[A의 흔적] = B의 흔적 개수로 진행하려고 했는데 덮어씌워주는 문제 떄문에 포기
• dp[A의 흔적][info 개수] = B의 흔적 개수로 진행하기로 결정
• dp[A의 흔적][info 개수]에 대해서도 중복되는 문제가 있지만, min 값으로 결정

 

 

#include <vector>

using namespace std;

int dp[121][41];

int solution(vector<vector<int>> info, int n, int m) {
    int answer = -1;
    
    for(int i = 0; i<=120; i++){
        for(int j = 0; j<=40; j++){
            dp[i][j]=987654321;
        }
    }
    
    dp[0][0]=info[0][1];
    dp[info[0][0]][0]=0;
    
    for(int i = 1 ; i<info.size(); i++){
        for(int j = 0; j<=120; j++){
            if(dp[j][i-1]!=-987654321){
                dp[j][i]=min(dp[j][i], dp[j][i-1]+info[i][1]);
                dp[j+info[i][0]][i]=min(dp[j+info[i][0]][i], dp[j][i-1]);
            }
        }
    }
    
    for(int i = 0; i<=120; i++){
        if(dp[i][info.size()-1]!=987654321 &&dp[i][info.size()-1] <m && i<n){
            answer = i;
            break;
        }
    }
    
    return answer;
}