[프로그래머스/LV2] [2025 프로그래머스 코드챌린지 2차 예선] 완전범죄 - bruteforce, dp (Java)

[프로그래머스/LV2] 완전범죄

🙋‍♂️ 들어가며

우선 문제는 A도둑의 흔적은 n개 미만, B도둑의 흔적을 m개 미만으로 유지한 상태에서 A도둑 흔적의 최솟값을 구해야한다.

아이템을 훔칠때 한 도둑이 그 아이템을 훔치면 다른 도둑은 그 아이템을 훔치지 못한다.

여기서 이 문제를 읽고 그리디는 반례가 존재할 것이라고 생각하였고, 경로의 경우의 수를 활용해서 해야한다고 생각하였다.

조건은 아래와 같다

• 1 <= info.length <= 40
• 1 <= traces <= 3
• 1 <= n <= 120
• 1 <= m <= 120

그래서 visited = new int[A의 흔적][B의 흔적]을 시작으로 visited, next_visited 배열을 두고 visited 배열에서 이동이 가능하면 next_visited에 이동된 좌표를 true로 설정하였고, 그 이후 visited로 갱신하고자 했다.

그리고 마지막에 2중반복문을 통해 가장 먼저 나오는 true가 어차피 A의 최소흔적값이니 알맞은 논리라고 생각했다

해당 알고리즘은 O(40 * 120 * 120) 으로 시간초과가 나지않고 충분히 통과할 수 있다고 생각했다.

이어서 내가 생각한 작동방식은 다음과 같다

testcase-1

info = {
    {1,2},
    {2,3},
    {2,1}
}

n = 4
m = 4
res = 2

조건은 현재 좌표에서 n, m보다 작을때 이동이 가능하다는 것이다

✅ 정답 코드 (bruteforce)

class Solution {
    public int solution(int[][] info, int n, int m) {
        
        // 시간복잡도 : O(l*n*m)
        boolean[][] visited = new boolean[n][m];
        
        // 1-1. 첫 값에 대입
        int first_trace_A = info[0][0];
        int first_trace_B = info[0][1];
        
        // 1-2. 훔칠 수 있다면 visited에 추가
        if (first_trace_A < n) {
            visited[first_trace_A][0] = true;
        }
        if (first_trace_B < m) {
            visited[0][first_trace_B] = true;
        }
        
        
        
        // 2. 각각 훔칠 수 있는지 검사
        for (int i = 1; i < info.length; i++) {
            int trace_A = info[i][0];
            int trace_B = info[i][1];
            boolean[][] next_visited = new boolean[n][m];
            boolean is_point_changed = false;
            
            // 2-1. A랑 B가 각각 더 훔칠 수 있는지 확인
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < m; c++) {
                    // 2-2. 이동가능한 상황일 때, 
                    if (visited[r][c] == true) {
                        // 2-2-a. A가 이동 가능하다면?
                        if (r + trace_A < n) {
                            next_visited[r + trace_A][c] = true;
                            is_point_changed = true;
                        }
                        // 2-2-b. B가 이동 가능하다면?
                        if (c + trace_B < m) {
                            next_visited[r][trace_B + c] = true;
                            is_point_changed = true;
                        }
                        
                    }
                }
            }
            
            // 2-3. 좌표 갱신 안됬으면 도둑 A,B 잡힌걸로 간주
            if (!is_point_changed) return -1;
            
            
            // 2-4. 좌표가 갱신되었다면 배열 갱신
            visited = next_visited;
        }


            
            
        
        
        
        // 3-1. 답 반환 : A의 최소흔적 (행이 제일 낮은거 반환)
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (visited[r][c] == true) {
                    return r;
                }
            }
        }
        
        // 3-2. 기본값 반환
        return -1;
    }
}

문제를 보니 DP도 가능하겠더라

B의 흔적이 x일때 A흔적의 최소값이다

m = 4 이기에 b의 흔적이 0일때, 1일때, 2일때, 3일때 A의 최솟값을 구할 수 있다

처음에는 DP_minA[m] 배열을 만들고, 모든 값을 INF로 채운 뒤, 첫값에 0을 넣는다. 처음에 둘다 안훔쳤기 떄문에 0을 넣은 것이다.

그렇게 되면 cur = {0, INF, INF, INF} 가 된다.

이제 반복문을 통해 다음과 같이 진행된다

testcase-1

i = 0
next = {I, I, I, I}
next = {1, I, 0, I}
cur = {1, I, 0, I}

b의 흔적이 0일때 A는 1개, B의 흔적이 2일때 A는 0개다


i = 1
next = {I, I, I, I}
next = {3, I, 2, I}
cur = {3, I, 2, I}

i = 2
next = {I, I, I, I}
next = {I, 3, I, 2}
cur = {I, 3, I, 2}

이것도 next가 m회만큼 바뀌지않았다면 -1을 return하는 조기종료 (최적화)가 가능하겠다

✅ 정답 코드 (DP)

class Solution {
    public int solution(int[][] info, int n, int m) {
        
        
        // 1. testcase 1번기준
        // b의 흔적이 0, 1, 2, 3일때 A의 최솟값
        int[] DP_minA = new int[m];
        
        // 2-1. 처음에 전부 INF로 채우기
        int I = Integer.MAX_VALUE;
        for (int r = 0; r < m; r++) {
            DP_minA[r] = I;
        }
        
        // 2-2. 초기값은 0, 처음에 둘다 안훔쳤기 때문에
        DP_minA[0] = 0;
        
        
        // 3. 검사
        for (int i = 0; i < info.length; i++) {
            int trace_A = info[i][0];
            int trace_B = info[i][1];
            
            // 3-1. next 배열 INF로 채우기
            int[] next = new int[m];
            for (int r = 0; r < m; r++) {
                next[r] = I;
            }
            
            // 3-2. b의 흔적이 m미만이고, j일때 A의 최소값
            for (int j = 0; j < m; j++) {
                // 3-3. 만약 이어서 A 혹은 B를 훔칠 수 없다면? -> continue;
                if (DP_minA[j] == I) continue;
                
                
                // 3-4. 만약 이어서 A 혹은 B를 훔칠 수 있다면?
                
                // 3-4-a. 만약 A를 훔칠 수 있다면?
                if (DP_minA[j] + trace_A < n) {
                    next[j] = Math.min(next[j], DP_minA[j] + trace_A);
                }
                
                // 3-4-b. 만약 B를 훔칠 수 있다면?
                if (j + trace_B < m) {
                    next[j + trace_B] = Math.min(next[j], DP_minA[j]);
                }
            }
            
            // 3-5. 최적화 (전부 INF면 더이상 못훔친다고 간주하고 조기종료)
            int cnt_INF = 0;
            for (int r = 0; r < m; r++) {
                if (next[r] == I) cnt_INF++;
            }
            if (cnt_INF == m) return -1;
            
            
            // 3-6. 그게 아니라면 갱신
            DP_minA = next;
        }
        
        
        
        // 4. 최소값 계산
        int answer = I;
        for (int r = 0; r < m; r++) {
            answer = Math.min(answer, DP_minA[r]);
        }
        return answer;
    }
}