출처 : 프로그래머스
난이도 : Level 2
문제 설명
A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 단, 각 도둑이 물건을 훔칠 때 남기는 흔적이 누적되면 경찰에 붙잡히기 때문에, 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.
물건을 훔칠 때 조건은 아래와 같습니다.
- 물건 i를 훔칠 때,
- A도둑이 훔치면 info[i][0]개의 A에 대한 흔적을 남깁니다.
- 각 물건에 대해 A도둑과 B도둑이 남기는 흔적의 개수는 1 이상 3 이하입니다.
경찰에 붙잡히는 조건은 아래와 같습니다.
- A도둑은 자신이 남긴 흔적의 누적 개수가 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
테스트 케이스 구성 안내
아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 테스트 케이스 그룹 설명 |
| #1 | 15% | info[i][1] = 1 |
| #2 | 40% | info의 길이 ≤ 20 |
| #3 | 45% | 추가 제한 사항 없음 |
입출력 예
| 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 |
입출력 예 설명
입출력 예 #1
첫 번째와 세 번째 물건을 B도둑이 훔치고 두 번째 물건을 A도둑이 훔치면, A도둑에 대한 흔적은 총 2개이고 B도둑에 대한 흔적은 총 3개입니다. 목표를 달성하면서 A도둑에 대한 흔적 개수를 2보다 더 낮게 만들 수 없습니다.
따라서 2를 return 해야 합니다.
입출력 예 #2
B도둑이 모든 물건을 훔쳐도 B의 흔적이 7개 이상 쌓이지 않습니다.
따라서 A도둑의 흔적은 최소 0이 되며, 0을 return 해야 합니다.
입출력 예 #3
B도둑이 한 번이라도 물건을 훔치면 B의 흔적이 최소 1개 이상 남습니다. 따라서 모든 물건을 A도둑이 훔쳐야 하며, 이 경우에도 A의 흔적은 7개 미만입니다.
따라서, A도둑이 모든 물건을 훔칠 때의 흔적 개수 6을 return 해야 합니다.
입출력 예 #4
어떤 방법으로도 두 도둑 모두 경찰에 붙잡히지 않고 모든 물건을 훔칠 수 없습니다.
따라서 -1을 return 해야 합니다.
----------------------------------------------------------------------------------------------------------------------------
문제 해독
A, B 도둑이 모든 물건을 훔칠때 A도둑의 흔적이 가장 적게 남기는 결과값
문제접근
첫번째 접근 : A도둑이 흔적을 많이 남기는 케이스를 내림차순으로 정렬하여 B도둑이 먼저 경찰에게 걸리는 최대치까지 흔적을 남긴 후 남은 물품에 대한 흔적을 A도둑의 흔적으로 할당
- 예외 발생 : 예제 케이스 1과 같은 케이스에서 B도둑에게 다른 조합으로 흔적을 채웠을때 더 낮은 A도둑의 흔적수를 구할 수 있음.
두번째 접근 : DFS 탐색을 통해 A도둑이 훔쳤을때 또는 B도둑이 훔쳤을때를 DFS 방식으로 탐색하여 모든 물건을 A, B 모두 경찰에 걸리지 않고 도달했을시의 A도둑의 총 흔적수를 저장(전역변수 int.MaxValue를 하나 두고 작은수를 들어가게 저장)
- 예외 발생 : 연산랑이 많아 시간 초과 문제 발생
세번째 접근 : DFS + Top-Down(DP) 방식으로 이전 호출 정보를 저장하여 중복 계산을 방지하여 불필요 연산을 제거
필요 변수 리스트
- minValue(int) : 최소 값 저장용. 초기값 MaxValue
- memo(Dictionary) : 이전 호출 정보 저장용
필요 알고리즘
- DFS
- DP
using System;
using System.Collections.Generic;
public class Solution {
private int minValue = int.MaxValue;
private Dictionary<(int,int,int), int> memo;
public int solution(int[,] info, int n, int m) {
memo = new Dictionary<(int,int,int), int>();
DFS(info, 0, 0, 0, n, m);
return minValue == int.MaxValue ? -1 : minValue;
}
private void DFS(int[,] info, int index, int a_cnt, int b_cnt, int n, int m)
{
if(a_cnt >= n || b_cnt >= m) return;
if(a_cnt >= minValue) return;
var key = (index, a_cnt, b_cnt);
if(memo.ContainsKey(key) && memo[key] <= a_cnt) return;
memo[key] = a_cnt;
if(index >= info.GetLength(0))
{
minValue = Math.Min(minValue, a_cnt);
return;
}
DFS(info, index + 1, a_cnt + info[index, 0], b_cnt, n, m);
DFS(info, index + 1, a_cnt, b_cnt + info[index, 1], n, m);
}
}