완전범죄

---

📌 문제 설명

A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 단, 각 도둑이 물건을 훔칠 때 남기는 흔적이 누적되면 경찰에 붙잡히기 때문에, 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.

물건을 훔칠 때 조건은 아래와 같습니다.

• 물건 i를 훔칠 때,
  • A도둑이 훔치면 info[i][0]개의 A에 대한 흔적을 남깁니다.
  • B도둑이 훔치면 info[i][1]개의 B에 대한 흔적을 남깁니다.
• 각 물건에 대해 A도둑과 B도둑이 남기는 흔적의 개수는 1 이상 3 이하입니다. 

 

경찰에 붙잡히는 조건은 아래와 같습니다.

• 도둑은 자신이 남긴 흔적의 누적 개수가 n개 이상이면 경찰에 붙잡힙니다.
• B도둑은 자신이 남긴 흔적의 누적 개수가 m개 이상이면 경찰에 붙잡힙니다.

 

각 물건을 훔칠 때 생기는 흔적에 대한 정보를 담은 2차원 정수 배열 info, A도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 n, B도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 m이 매개변수로 주어집니다. 두 도둑 모두 경찰에 붙잡히지 않도록 모든 물건을 훔쳤을 때, A도둑이 남긴 흔적의 누적 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 어떠한 방법으로도 두 도둑 모두 경찰에 붙잡히지 않게 할 수 없다면 -1을 return해 주세요.

 

📌 제한 사항

• 1 ≤ info의 길이 ≤ 40
  • info[i]는 물건 i를 훔칠 때 생기는 흔적의 개수를 나타내며, [A에 대한 흔적 개수, B에 대한 흔적 개수]의 형태입니다.
  • 1 ≤ 흔적 개수 ≤ 3
• 1 ≤ n ≤ 120
• 1 ≤ m ≤ 120

 

📌 입출력 예

info	n	m	result
[[1, 2], [2, 3], [2, 1]]	4	4	2
[[1, 2], [2, 3], [2, 1]]	1	7	0
[[3, 3], [3, 3]]	7	1	6
[[3, 3], [3, 3]]	6	1	-1

 

🔗 문제 링크

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

프로그래머스

---

반응형

💡 풀이 아이디어

• 동적 계획법

📝 최종 풀이

• 상태 정의
  • 각 물건을 A 도둑 또는 B 도둑이 훔쳤을 때 누적 흔적을 추적해야한다.
  • dp[i][a][b]= i 번째 물건까지 고려했을 A의 누적흔적이 a이고, B의 누적흔적이 b일 때, A가 남긴 최소 누적 흔적 값
  • 초기값 dp[0][0][0] = 0은 아무 물건도 훔치지 않았을 때 두 도둑의 누적 흔적은 0, 나머지는 121로 초기화
• 점화식
  
  • i+1번째 물건까지 고려했을 때 최소 A 도둑 흔적 값은, i번째 물건까지 고려했을 때의 최소 A 도둑 흔적 값에 현재 물건을 훔치면서 발생한 A 도둑의 흔적을 더한 값과 현재 저장된 값 중 더 작은 값으로 업데이트

---

728x90

👩‍💻 코드

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

using namespace std;

int solution(vector<vector<int>> info, int n, int m) {
    int answer = 121;
    int info_size = info.size();
    vector<vector<vector<int>>> dp(info_size + 1, vector<vector<int>>(n, vector<int>(m, 121)));
    
    dp[0][0][0] = 0;
    
    for (int i=0; i<info_size; i++){
        int a_current = info[i][0];
        int b_current = info[i][1];
        
        for (int a_index = 0; a_index < n; a_index++){
            for (int b_index = 0; b_index < m; b_index++){
                if (dp[i][a_index][b_index] == 121){
                    continue;
                }
                
                if(a_index + a_current < n){
                    dp[i+1][a_index+a_current][b_index] = min(dp[i + 1][a_index + a_current][b_index], dp[i][a_index][b_index] + a_current);
                }
                
                if (b_index + b_current < m) {
                    dp[i + 1][a_index][b_index + b_current] = min(dp[i + 1][a_index][b_index + b_current], dp[i][a_index][b_index]);
                }
            }
        }
    }
    
    for(int a_index = 0; a_index < n; a_index++){
        for(int b_index = 0; b_index < m; b_index++){
            answer = min(answer, dp[info_size][a_index][b_index]);
        }
    }
    
    return (answer == 121) ? -1 : answer;
}