[프로그래머스/Kotlin]Lv2 - 완전범죄

프로그래머스

문제 해석

문제 설명

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

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

• 물건 i를 훔칠 때,
  • A도둑이 훔치면 info[i][0]개의 A에 대한 흔적을 남깁니다.
  • B도둑이 훔치면 info[i][1]개의 B에 대한 흔적을 남깁니다.
• 각 물건에 대해 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 해야 합니다.

---

풀이 방법

풀이 접근 과정

처음엔 완전 탐색 느낌으로 DFS를 이용하여 깊이 우선 탐색을 진행했다.

그냥 모든 경우의 수에 맞춰 최솟값을 계산하면 되지 않나? 하는 막연한 생각이었다.

 

하지만 이 방식에서는 중복 처리를 하지 못해 시간 초과가 발생…

결국 DP 방식과 결합하여 코드를 짰다. (DP만으로는 도저히 모르겠음 ㅋㅋㅋㅋ)

정확하게는 메모제이션 코드라고 함…ㅎㅎ

최종 소스코드

import kotlin.math.min

class Solution {
    fun solution(info: Array<IntArray>, n: Int, m: Int): Int {
        var answer: Int = Int.MAX_VALUE

        val dp = Array(info.size) { Array(n) { IntArray(m) { -1 } } } // [index, a, b]

        fun dfs(index: Int, a: Int, b: Int) {
            if (index <= info.lastIndex) {
                val aValue = a+info[index][0]
                if (aValue < n && dp[index][aValue][b] == -1) {
                    dp[index][aValue][b] = 0
                    dfs(index+1, aValue, b)
                }

                val bValue = b+info[index][1]
                if (bValue < m && dp[index][a][bValue] == -1) {
                    dp[index][a][bValue] = 0
                    dfs(index+1, a, bValue)
                }
            } else {
                answer = min(a,answer)
            }
        }

        dfs(0, 0, 0)

        return if (answer == Int.MAX_VALUE) -1 else answer
    }
}

1. index, a, b의 값을 저장할 DP 3차원 배열을 선언한다.
2. 재귀 함수를 돌리면서 도둑이 물건을 훔치는 모든 경우의 수를 계산한다.
   1. 현재 index에서 a의 값과 b의 값이 유효한 경우가 이미 존재하면 중복계산이니 패스한다.
3. 최솟값 계산하여 리턴

---

Comment

나는 DP가 고도화 되면 제일 헷갈리고 어려움 ㅋ큐ㅜㅠㅜㅠ