문제 링크

성능 요약

메모리: 88.7 MB, 시간: 0.38 ms

구분

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

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2025년 03월 04일 13:46:06

문제 설명

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 해야 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

풀이

느낀점

• 배낭 알고리즘을 안다면 응용해볼 수 있는 문제다.
• 다만, dp 구현기준이 헷갈려서 고민하는데 조금 오래걸렸다.

설계 : 30분

• B가 남길 수 있는 흔적 값을 기준으로 A가 최소로 남기는 흔적을 dp테이블로 만들었다.
• 먼저 [Info.length][m] 사이즈로 dp테이블을 생성한다.
• 각 물건을 추가로 사용해가며, B가 m보다 적게 흔적을 남기는 경우를 확인한다.
• i번째 물건을 훔칠때 B가 흔적을 남길 수 있는 칸이라면 i-1번 물건까지 훔쳤을때의 경우에서 i번째 물건을 B가 훔치는 경우와, B가 훔치지 않는 경우를 비교하여 A가 흔적을 더 적게 남기는 경우로 갱신한다.
  • 즉, dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-(B가 남기는 흔적)] - (A가 남기는 흔적)
• B가 물건을 훔칠 수 없는 경우에는 i-1번 물건까지의 상태값을 그대로 가져온다.

코드(Java)

• 구현 시간: 30분

import java.lang.*;

class Solution {
    public int solution(int[][] info, int n, int m) {
        
        int cnt = info.length;
        
        // 행 인덱스: 물건의 번호, 열 인덱스: B가 남길 수 있는 흔적의 한계
        // value: A가 남길 수 있는 최소의 흔적
        int[][] dp = new int[cnt][m];
        
        // 모든 물건을 A가 훔치는 경우의 값
        int max = 0;
        for (int i = 0; i < cnt; i++) max += info[i][0];
        
        // 0번 인덱스 물건 초기화
        // B가 물건을 훔칠 수 있는 부분부터 value에서 A의 흔적 값을 지워 최소값 갱신
        for (int j = 0;j < m; j++) {
            if (j < info[0][1]) dp[0][j] = max;
            else dp[0][j] = max - info[0][0];
        }
        
        for (int i = 1; i < cnt; i++) {
            for (int j = 0; j < m; j++) {
                if (j < info[i][1]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-info[i][1]] - info[i][0]);
            }
        }
        
        // 최종 값이 n 이상일 경우, 가능한 경우가 없다는 뜻
        if (dp[cnt - 1][m - 1] >= n) return -1;
        return dp[cnt - 1][m-1];
    }
}