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

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 99999;

int solution(vector<vector<int>> info, int n, int m) {
    int size = info.size();

    vector<vector<int>> dp(size+1, vector<int>(m, INF));
    dp[0][0] = 0;

    for (int i = 0; i < size; i++) 
    {
        auto tmp = dp;
        for(int j=0; j<m; j++)
        {
            if(dp[i][j]==INF) continue;
            
            int a = dp[i][j] + info[i][0]; //a의 흔적
            if(a < n) tmp[i+1][j] = min(tmp[i+1][j], a); 
            
            int b = j + info[i][1]; //b의 흔적
            if(b < m) tmp[i+1][b] = min(tmp[i+1][b], dp[i][j]);
        }
        dp = tmp;
    }

    int result = *min_element(dp[size].begin(),dp[size].end());
    return result == INF ? -1 : result;
}

 

그리디하게 접근하여 풀 수 있는 문제이다.

먼저 정렬을 a가 맡으면 손해인 물건이 우선시되게 정렬해준다.

기본적으로 각 흔적의 차이를 계산하여, a가 훔쳤을 때 차이가 더 큰 값 우선으로 정렬하게 된다.

차이가 아에 같은 경우도 발생할 수 있는데, 이는 비율을 계산하여 정렬해준다.

 

이후에는 간단하게 b가 가능한 경우 b부터 누적합을 우선시해서 구해주고, 이후에 a에 대해서도 누적합을 구해주면 된다.

만약 둘다 불가능하면 바로 -1을 반환한다.

이러면 자연스럽게 b가 우선시해서 a가 맡으면 손해인 물건을 훔치게 되며, 남은 걸 a가 훔치게 된다.

 

<다른 풀이>

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 99999;

int solution(vector<vector<int>> info, int n, int m) {
    int size = info.size();

    vector<vector<int>> dp(size+1, vector<int>(m, INF));
    dp[0][0] = 0;

    for (int i = 0; i < size; i++) 
    {
        auto tmp = dp;
        for(int j=0; j<m; j++)
        {
            if(dp[i][j]==INF) continue;
            
            int a = dp[i][j] + info[i][0]; //a의 흔적
            if(a < n) tmp[i+1][j] = min(tmp[i+1][j], a); 
            
            int b = j + info[i][1]; //b의 흔적
            if(b < m) tmp[i+1][b] = min(tmp[i+1][b], dp[i][j]);
        }
        dp = tmp;
    }

    int result = *min_element(dp[size].begin(),dp[size].end());
    return result == INF ? -1 : result;
}

 

dp로도 풀 수 있다.

dp[i][j]은 i번째까지 물건을 분배했을 때 B가 맡은 흔적 총합이 j일 때, A가 맡은 흔적 최소합이다.

 

먼저 갱신용 dp를 따로 선언해주어야 한다.

그냥 dp 하나만 가지고 갱신할 때, 이전에 [i+1][j] 등을 통해 값을 갱신하기에, 이후 계산해서 값이 오염된 상태로 진행될 수 있다.

먼저 a에 대해서는 간단하게 dp[i][j] + info[i][0]이다.

이를 토대로 흔적 값이 n이하여서 갱신이 가능할 때, [i+1][j]에 대해 최소값을 비교하여 갱신한다.

 

b의 경우 반복문의 j가 흔적 값이기에 j + info[i][1]이다.

이를 토대로 흔적 값이 m이하여서 갱신이 가능할 때, 현재 흔적에 대한 dp[i][j]과 계산한 흔적 량에 대한 tmp[i+1][b]와 최소값을 비교한다.

 

이를 토대로 저장된 dp[size] 값에서 b에 대한 흔적들 중 최소값을 반환해주면 된다.