[1일 1알고] 완전 범죄

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

프로그래머스

 

이번 문제는 DP문제입니다.

보면 A혹은 B도둑이 물건을 훔치는 경우를 고려해야하는데 depth가 최대 40이므로 dfs 등 완전탐색 기반의 알고리즘을 사용하기에는 무리가 있습니다. 따라서 일단 DP방식을 생각해야합니다.

 

필요한 정보는 현재 시점에서 a가 남긴 흔적, b가 남긴 흔적입니다.

그런데 하나의 이차원 배열로만 상태를 관리하기에는 이전의 상태만 고려해야하지 그보다 이전의 상태는 고려하면 안되기 때문에 두 개의 배열을 통해 왔다갔다 하도록 했습니다.

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>
#include <climits>
#include <unordered_map>
using namespace std;

// A도둑, B도둑은 붙잡히지 않도록 흔적을 최소화
// 물건 i를 훔칠 때 
// -> A도둑이라면 info[i][0], B도둑이라면 info[i][1]
// 각 물건에 대해 남기는 흔적은 1이상 3이하
// A도둑은 n개"이상"이면 잡힘, B도둑은 m개이상이면 잡힘
// 둘다 붙잡히지 않았을 때 A도둑이 남긴 흔적의 최솟값


int solution(vector<vector<int>> info, int n, int m) {
    int answer = 0;

    vector<int> state1(121, 121);
    vector<int> state2(121, 121);
    state1[info[0][0]] = 0;
    state1[0] = info[0][1];

    for (int i = 0; i < info.size(); ++i)
    {
        if (i % 2 == 0)
        {
            for (int j = 0; j <= 120; ++j)
            {
                if (state2[j] != 121)
                {
                    if (j + info[i][0] < n) // A가 훔침
                        state1[j + info[i][0]] = min(state1[j + info[i][0]], state2[j]); // 이전 B + 

                    if (state2[j] + info[i][1] < m) // B가 훔침
                        state1[j] = min(state1[j], state2[j] + info[i][1]);
                }
            }
            if (i == info.size() - 1)
            {
                for (int j = 0; j < n; ++j)
                {
                    if (state1[j] < m)
                        return j;
                }
                return -1;
            }
            fill(state2.begin(), state2.end(), 121);
        }
        else
        {
            for (int j = 0; j <= 120; ++j)
            {
                if (state1[j] != 121)
                {
                    if (j + info[i][0] < n) // A가 훔침
                        state2[j + info[i][0]] = min(state2[j+info[i][0]], state1[j]); // 이전 B + 

                    if (state1[j] + info[i][1] < m) // B가 훔침
                        state2[j] = min(state2[j], state1[j] + info[i][1]);
                }
            }
            if (i == info.size() - 1)
            {
                for (int j = 0; j < n; ++j)
                {
                    if (state2[j] < m)
                        return j;
                }
                return -1;
            }
            fill(state1.begin(), state1.end(), 121);
        }
    }

    return answer;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n = 4, m = 4;
    vector<vector<int>> info = { {1, 2}, {2, 3}, {2, 1} };

    solution(info, n, m);
    return 0;
}

전부 만들고 보니 0/1 knapsack처럼 풀었으면 간단했겠네요 ㅠㅠ