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

요구사항

A도둑과 B도둑이 정해진 물건을 훔칠 때 남기는 흔적이 주어지고 각각 정해진 최대 누적 흔적을 초과하는 경우 경찰에 붙잡힌다.

두 도둑이 경찰에 붙잡히지 않도록 물건을 훔칠 때 A도둑이 남길수 있는 최소한의 흔적 구하기.

(붙잡히지 않고 훔치기가 불가능한 경우에는 -1을 반환)

 

 

입력 값

int[][] info	도둑이 훔쳐야 하는 물건의 상세 정보 info[i][0]은 i+1 번째 물건을 A도둑이 훔칠 때 남는 흔적 info[i][1]은 i+1 번째 물건을 B도둑이 훔칠 때 남는 흔적
int n	A도둑이 경찰에 붙잡히는 최소 흔적 개수
int m	B도둑이 경찰에 붙잡히는 최소 흔적 개수

 

 

풀이

1. 누적 흔적을 저장할 배열 dp와 최대 누적 값으로 사용 할 수 있는 maxVal 생성

    -> dp는 초기값(=물건 훔치기 전) [0][0] 세팅을 위해 info 배열보다 1씩 크게 생성

    -> maxVal 은 추후 흔적 수 비교에 사용될 예정으로, 문제의 최대 흔적수와 동일하게 생성

 

2. 각 아이템 별로 흔적 경우의 수 저장

    -> 이 물건을 훔칠 수 있는 도둑의 경우 다음 누적 탐색 저장

        (도둑별 현재 물건의 흔적 수 + 도둑별 누적 흔적 < 경찰에 붙잡히는 흔적수)

    -> 불필요한 재탐색 방지를 위해 탐색한 dp는 false 처리

 

3. 2번 반복 중 마지막 물건인 경우 해당 시점의 A 도둑의 흔적 수로 비교하여 Minimum 값 구하기

 

4. 구한 minimum 값 return

    -> minimum 값이 초기 설정한 최대값과 동일 한 경우 모든 물건 훔치기 실패한 것이므로 -1 return

 

728x90

 

Java 코드

class Solution {
    public int solution(int[][] info, int n, int m) {
        int answer = 0;
        
        boolean[][] dp = new boolean[n+1][m+1];
        int maxVal = 120;
        int result = maxVal;
        
        // 초기 값 설정
        dp[0][0] = true;

        for (int i=0; i<info.length; i++) {
            int aTrace = info[i][0];
            int bTrace = info[i][1];
            
            for (int a=n; a>=0; a--) {
                for (int b=m; b>=0; b--) {
                    if(!dp[a][b]) continue;

                    // A가 이 물건을 훔칠 경우 저장
                    if (a + aTrace < n) {
                        dp[a + aTrace][b] = true;
                        if((i+1) == info.length) result = Math.min(a + aTrace, result);
                    }
                    // B가 이 물건을 훔칠 경우 저장
                    if (b + bTrace < m) {
                        dp[a][b + bTrace] = true;
                        if((i+1) == info.length) result = Math.min(a, result);
                    }
                    
                    dp[a][b] = false;
                }
            }
        }

        return result == maxVal ? -1 : result;
    }
}

 

 

문제 출처

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