[JAVA] 프로그래머스 LEVEL2 완전범죄

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

프로그래머스

코딩테스트 연습 > 2025 프로그래머스 코드챌린지 2차 예선 > 완전 범죄

 

난이도: LEVEL2

알고리즘 유형: 다이나믹 프로그래밍 - DP

 

완전 탐색 풀이 

import java.util.*;
class Solution {
    static int answer = Integer.MAX_VALUE;
    static int N,M,size;
    public int solution(int[][] info, int n, int m) {
        N = n; M = m; size = info.length;
        int b_sum = 0;
        for(int i = 0; i < size; i++){
            b_sum += info[i][1];
        }
        func(info, 0, 0, b_sum);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    public static void func(int [][] info, int depth, int a_sum, int b_sum){
        if(a_sum >= answer) return;
        if(a_sum < N && b_sum < M){
            answer = Math.min(answer, a_sum);
            return;
        }
        if(size == depth) return;
        func(info, depth + 1, a_sum, b_sum);
        func(info, depth + 1, a_sum + info[depth][0], b_sum - info[depth][1]);
    }
}

 

처음 시도했던 완전 탐색 풀이다.

info의 40으로 길이가 작아서 완전 탐색으로 풀려고 했는데 시간 초과가 발생하여 40점이 나온다.

생각을 해보면 완전 탐색 풀이는 최악의 경우 2^40 시간 복잡도가 발생하여 대략 1조의 연산이 수행된다.

완전 탐색으로 풀이가 불가능한 경우 2가지 풀이로 나뉜다. 그리디 or 다아니믹 프로그래밍 

 

하지만 그리디 풀이는 이번 문제를 통과하지 못한다. 

A의 흔적의 개수가 작은 순서대로 정렬을 하고 선택했을 때 A의 최솟값이 나오지 않기 때문이다. 

 

ex)

[1, 2], [2, 3], [3, 2] [4, 7]  n = 7 m = 8 가정

그리디로 풀게 되면 정답은 6이 된다 A의 흔적 개수가 6이 될 때 14 - 7 = 7 B의 흔적 개수가 7이 되어 통과되지만

정답은 A의 흔적 개수가 4일 때 14 - 7 = 7이 되어서 조건을 만족하여 4가 정답이다.

 

다이나믹 프로그래밍 풀이

import java.util.*;
class Solution {
    static final int INF = 100000;
    public int solution(int[][] info, int n, int m) {
        int size = info.length;
        int [][] dp = new int [size+1][m];
        for(int i = 0; i <= size; i++){
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = 0;
        for(int i = 1; i <= size; i++){
            int a = info[i-1][0];
            int b = info[i-1][1];
            for(int j = 0; j < m; j++){
                // a 선택 
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + a);
                // b 선택
                if(j + b < m){
                    dp[i][j + b] = Math.min(dp[i][j + b], dp[i-1][j]);
                }
            }    
        }
        int min = INF;
        for(int j = 0; j < m; j++){
            min = Math.min(dp[size][j], min);
        }
        return min >= n ? -1 : min;
    }
}

 

2차원 배열 점화식 dp[x][y]: z

물건 훔친 개수가 x이고 B도둑의 흔적 개수가 y일 때 A의 도둑의 최소 흔적 개수(z)이다.

 

A도둑이 남긴 흔적이 n보다 작아야 하고 B도둑이 남긴 흔적이 m보다 작아야 한다. 

즉, 그래서 행을 훔친 물건의 개수로 잡고 열의 최대 크기를 m-1로 잡는다.

 

b의 흔적 개수 0 <= 흔적 개수 < m 즉, b가 허용 가능한 흔적 개수를 for문을 돌면서 선택을 한다. 

 

이번 물건의 가중치: A도둑이 훔친다면 a B도둑이 훔친다면 b

 

2가지 경우가 존재한다.

1. 이번 물건은 A도둑이 훔친다. 

2. 이번 물건은 B도둑이 훔친다.

 

1번의 경우

dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + a);

B도둑의 흔적 개수(j)는 이전 훔친 물건의 개수에서 그대로 A도둑의 흔적 개수는 a만큼 늘려준다.

 

2번의 경우

dp[i][j + b] = Math.min(dp[i][j + b], dp[i-1][j]);

B도둑의 흔적 개수(j)를 늘린고 A도둑의 흔적 개수는 이전 훔친 물건 개수에서 그대로 가져온다.

 

dp 갱신이 끝나면 정답을 찾는다.

모든 물건을 훔친 상태에서 A의 최소 흔적 개수를 찾는다. 

dp의 모든 열은 모두 B가 정상적으로 훔치는 게 가능한 허용 범위인 m 이내의 값만 기록하여서 min 값만 갱신하면 끝이다.

 

만약 최종적으로 찾은 A의 최소 흔적 개수가 n보다 크면 -1을 반환하고 아니라면 그대로 최소 흔적 개수를 반환한다. 

 

시간 복잡도는 info의 크기 * m의 크기 

최악의 경우 info의 크기가 40 * m의 크기가 120:  40 * 120의 매우 빠른 연산이 가능하다.  

결과 

테스트 1 〉	통과 (0.08ms, 77.1MB)
테스트 2 〉	통과 (0.09ms, 74.1MB)
테스트 3 〉	통과 (0.05ms, 70.1MB)
테스트 4 〉	통과 (0.19ms, 80.7MB)
테스트 5 〉	통과 (0.18ms, 72.9MB)
테스트 6 〉	통과 (0.11ms, 77.4MB)
테스트 7 〉	통과 (0.14ms, 74.3MB)
테스트 8 〉	통과 (0.32ms, 87.7MB)
테스트 9 〉	통과 (0.15ms, 68.4MB)
테스트 10 〉	통과 (0.13ms, 84.7MB)
테스트 11 〉	통과 (0.05ms, 78.3MB)
테스트 12 〉	통과 (0.07ms, 93.9MB)
테스트 13 〉	통과 (0.05ms, 75.7MB)
테스트 14 〉	통과 (0.04ms, 85.3MB)
테스트 15 〉	통과 (0.19ms, 83.5MB)
테스트 16 〉	통과 (0.09ms, 83.1MB)
테스트 17 〉	통과 (0.10ms, 86.1MB)
테스트 18 〉	통과 (0.05ms, 80.9MB)
테스트 19 〉	통과 (0.09ms, 79.6MB)
테스트 20 〉	통과 (0.14ms, 81.9MB)
테스트 21 〉	통과 (0.05ms, 89.1MB)
테스트 22 〉	통과 (0.08ms, 75.8MB)
테스트 23 〉	통과 (0.10ms, 80.3MB)
테스트 24 〉	통과 (0.18ms, 86.8MB)
테스트 25 〉	통과 (0.53ms, 80MB)
테스트 26 〉	통과 (0.19ms, 85.1MB)
테스트 27 〉	통과 (0.39ms, 86.4MB)
테스트 28 〉	통과 (0.45ms, 81.7MB)
테스트 29 〉	통과 (0.18ms, 73.3MB)
테스트 30 〉	통과 (0.49ms, 73.3MB)
테스트 31 〉	통과 (0.13ms, 86.1MB)
테스트 32 〉	통과 (0.53ms, 81.2MB)
테스트 33 〉	통과 (0.31ms, 76MB)
테스트 34 〉	통과 (0.24ms, 75.4MB)
테스트 35 〉	통과 (0.14ms, 73.6MB)
테스트 36 〉	통과 (0.28ms, 73.7MB)
테스트 37 〉	통과 (0.15ms, 92.2MB)
테스트 38 〉	통과 (0.04ms, 79.2MB)
테스트 39 〉	통과 (0.03ms, 84.4MB)