[programmers-lv2] 완전범죄

[2025 프로그래머스 코드챌린지 2차 예선] 완전범죄

🙋‍♂️ 들어가며

이 문제는 A도둑, B도둑이 존재하는데 각각 누적 흔적의 갯수가 n, m보다 작은 상황에서 훔치며 최종적으로 A도둑이 남긴 누적 흔적횟수를 구해야 한다.

2가지 방법으로 구할 수 있겠다

• bruteforce
• DP

bruteforce 접근법

• A가 훔치면 B는 못 훔치고
• B가 훔치면 A는 못 훔치고

즉 O, X 식으로 만들어보자

testcase

info = { {1,2}, {2,3}, {2,1} }
n = 4;
m = 4;

result = 2

먼저 처음은 누구도 어떤 것도 훔치지 않았기에 DP[0][0] = 0

{
    {o, x, x, x},
    {x, x, x, x},
    {x, x, x, x},
    {x, x, x, x}
}

완전탐색을 통해 DP[i][j] != false 일때 (더 훔치러 갈 수 있다는 뜻)

만약 다음과 같은 조건에 맞다면

• i + a_trace < n
• j + b_trace < m

info[0] = {1,2}

• A가 훔치면 DP[1][0] = true
• B가 훔치면 DP[0][2] = true

가능한 지점은 DP[1][0], DP[0][2] 로 총 2가지가 된다

이어서 1번째 idx를 보며 마찬가지로 조건에 맞는지 확인

• info[1] = {2,3}
• i + a_trace < n
• j + b_trace < m

A가 훔치면

• DP[3][0] = true
• DP[2][2] = true

B가 훔치면

• DP[1][3] = true

이어서 2번째 idx를 보자 info[2] = {2,1}

가능한 지점은 DP[3][0], DP[2][2], DP[1][3]

A가 훔치면

• DP[3][3] = true

B가 훔치면

• DP[3][1] = true
• DP[2][3] = true

이제 훔치는건 전부 종료되었다.

지금부터 우리가 구해야할 것은 A의 최소 누적흔적이니 완전탐색을 통해 true인 것중 i만 반환하고 return하면 되겠다. 그렇다면 위 testcase 기준으로 DP[2][3]의 2를 반환할 것이다.

그 외는 -1을 return한다.

여기까지의 연산시간은 다음과 같겠다.

O(l * n * m) = info 길이 * n * m

✅ 코드 (bruteforce)

class Solution {
    public int solution(int[][] info, int n, int m) {
        
        // 1. 2차원 배열 생성
        boolean[][] DP = new boolean[n][m];
        
        // 2. 초기값, 처음에 A,B 누구도 어떤 것도 훔치지 않았다
        DP[0][0] = true;
        
        // 3. 검사
        for (int[] cur : info) {
            int a_trace = cur[0];
            int b_trace = cur[1];
            
            // 3-1. 새로운 배열
            boolean[][] next_DP = new boolean[n][m];
            
            // 3-2. 완전탐색
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    // 3-3. 방문 안했으면 skip (도둑질한 현황이 없다는 뜻)
                    if (!DP[i][j]) continue;
                    
                    // 3-4. A 혹은 B가 도둑질한 현황이 있다면
                    
                    // 3-5. A의 흔적을 더 남길 수 있다면
                    if (i + a_trace < n) {
                        next_DP[i + a_trace][j] = true;
                    }
                    
                    // 3-6. B의 흔적을 더 남길 수 있다면
                    if (j + b_trace < m) {
                        next_DP[i][j + b_trace] = true;
                    }
                }
            }
            // 4. 갱신
            DP = next_DP;
        }
        
        
        // 5. A의 누적 최소흔적 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (DP[i][j]) {
                    return i;
                }
            }
        }
        
        // 6. A의 누적최소흔적이 없다면
        return -1;
    }
}

그러면 다른 방법인 1차원으로 줄인 DP도 가능하지 않을까?

• B의 흔적이 x 일때 최소 A의 흔적

DP 접근법

B를 고른 갯수 기준으로 각 A의 누적흔적 최소를 만들자

그래서 배열의 크기는

int[] DP = new int[m];

그리고 INF로 전부 초기화하고 맨처음값은 0을 넣자

그리고 상태 갱신을 위해 매 info 반복마다 next_DP 를 만들며 마찬가지로 INF로 전부 초기화하자

testcase

info = { {1,2}, {2,3}, {2,1} }
n = 4;
m = 4;

result = 2

여기서 INF를 활용해 DP[i] == INF 라면 훔치는게 이어지지 못하는거니 skip

info idx -> 0일때

DP = {0, INF, INF, INF};
next_DP = {INF, INF, INF, INF}

->

next_DP = {1, INF, 0, INF}

-> 

DP = {1, INF, 0, INF}

• B = 0일때 A = 1
• B = 2일때 A = 0

info idx -> 1일때

DP = {1, INF, 0, INF}
next_DP = {INF, INF, INF, INF}

->

next_DP = {3, INF, 2, 1}

• B = 0일때 A += 2
• B = 2일때 A += 2
• B = 3 일때 A = 1 (idx 1일때 B도둑이 흔적을 3남겼다면 당연히 최소값으로는 idx 0일때 A도둑이 흔적 1을 남긴것)

info idx -> 2일때

DP = {3, INF, 2, 1}
next_DP = {INF, INF, INF, INF}

->

next_DP = {INF, 3, INF, 2}

j = 0일때 info[2][1] 고르면 B는 1개 훔친거니 A는 당연히 3개가 되야한다

이후 j = 1일때 INF라서 skip

j = 2일때 info[2][1] 고르면 B는 3개 훔치는게 되고, 그때 A의 최솟값은 2

j = 3일때 DP[3] = 1, info[2][1] = 2 이것들을 더하면 3 -> 즉 더크니 skip

최종

answer = INF 를 생성하고

1중 for문을 통해 DP[i] 값과 비교하며 마지막으로 answer == INF 라면 return -1

그게 아니라면 return answer

✅ 코드 (DP)

class Solution {
    static int INF = Integer.MAX_VALUE;
    
    
    public int solution(int[][] info, int n, int m) {
        
        // 1. B기준으로 각 A의 누적흔적 최소
        int[] DP = new int[m];
        
        // 2. INF 로 초기화하고, 첫값은 0
        for (int i = 0; i < m; i++) {
            DP[i] = INF;
        }
        DP[0] = 0;
        
        // 3. 검사
        for (int[] cur : info) {
            int a_trace = cur[0];
            int b_trace = cur[1];
            
            // 3-1. 다음 DP 생성하고, INF 초기화
            int[] next_DP = new int[m];
            for (int i = 0; i < m; i++) {
                next_DP[i] = INF;
            }
            
            
            // 3-2. 최소값 갱신
            for (int i = 0; i < m; i++) {
                // 3-1. 만약 훔치는게 이어지지 못하면 skip
                if (DP[i] == INF) continue;
                
                // 3-2. 그게 아니라면
                
                // 3-3. a흔적을 더 남길 수 있다면
                if (DP[i] + a_trace < n) {
                    next_DP[i] = Math.min(next_DP[i], DP[i] + a_trace);
                }
                
                // 3-4. b흔적을 더 남길 수 있다면
                if (i + b_trace < m) {
                    next_DP[i + b_trace] = Math.min(next_DP[i + b_trace], DP[i]);
                }
            }
            
            // 4. 갱신
            DP = next_DP;
        }
        
        // 5-1. 출력 (음수처리)
        int answer = INF;
        for (int i = 0; i < m; i++) {
            answer = Math.min(DP[i], answer);
        }
        if (answer == INF) return -1;
        
        // 5-2. 출력 (음수가 아닐때)
        return answer;
    }
}