완전범죄 (Java)

🔗 문제 링크

---

📝 문제 설명

A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 하지만 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.

• 물건을 훔칠 때:
  • A도둑이 훔치면 info[i][0]개의 A의 흔적이 남습니다.
  • B도둑이 훔치면 info[i][1]개의 B의 흔적이 남습니다.
• 조건:
  • A도둑의 흔적 합이 n 이상이면 체포됩니다.
  • B도둑의 흔적 합이 m 이상이면 체포됩니다.
• 목표: 모든 물건을 훔치되 A도둑이 남긴 흔적의 합을 최소화해야 합니다.

---

✅ 풀이 과정

1️⃣ 첫 번째 시도: 정렬을 통한 탐욕법 (Greedy)

접근법:
1. 내림차순 정렬: A도둑의 흔적이 큰 순서로 정렬하되, 같으면 B의 흔적이 작은 순서로 정렬합니다.
2. 각 물건에 대해:

• B도둑이 먼저 시도: B의 흔적 합이 m 미만이면 B가 훔침
• 그렇지 않으면 A가 훔침

private int descFirstAscSecond(int[][] info, int n, int m) {
    int answer = 0;
    Arrays.sort(info, (o1, o2) -> {
        if (o1[0] == o2[0]) return o1[1] - o2[1];
        return -(o1[0] - o2[0]);
    });

    for (int[] item : info) {
        if (m - item[1] > 0) m -= item[1];
        else {
            if (n - item[0] > 0) {
                n -= item[0];
                answer += item[0];
            } else return -1;
        }
    }
    return answer;
}

2️⃣ 두 번째 시도: 두 가지 정렬 방식 혼합

접근법:
1. 첫 번째는 내림차순 정렬을 사용
2. 두 번째는 오름차순 정렬을 사용
3. 두 결과 중 더 작은 값을 선택

public int solution(int[][] info, int n, int m) {
    int answer1 = descFirstAscSecond(info, n, m);
    int answer2 = ascFirstAscSecond(info, n, m);

    if (answer1 == -1) return answer2;
    if (answer2 == -1) return answer1;

    return Math.min(answer1, answer2);
}

private int ascFirstAscSecond(int[][] info, int n, int m) {
    int answer = 0;
    Arrays.sort(info, (o1, o2) -> {
        if (o1[0] == o2[0]) return o1[1] - o2[1];
        return o1[0] - o2[0];
    });

    for (int[] item : info) {
        if (m - item[1] > 0) m -= item[1];
        else {
            if (n - item[0] > 0) {
                n -= item[0];
                answer += item[0];
            } else return -1;
        }
    }
    return answer;
}

❗ 문제점:

• Greedy 접근법은 항상 최적의 해를 보장하지 않음
• 일부 케이스에서는 더 작은 흔적의 조합이 가능함

---

💡 3️⃣ 세 번째 시도: Dynamic Programming (DP)

접근법:

• 목표: A도둑의 흔적을 최소화하면서 B도둑의 흔적이 m 미만이어야 함
• 배열 정의:
  • dp[i][b]: i번째 물건까지 고려했을 때, B의 흔적이 b일 때, A의 최소 흔적 합

초기화:

• dp[0][0] = 0 (시작 시 흔적 없음)
• 나머지는 n으로 초기화 (A도둑이 최대로 남길 수 있는 흔적)

점화식:

• A도둑이 물건을 훔칠 때:
  • dp[i][b] = min(dp[i][b], dp[i-1][b] + A의 흔적)
• B도둑이 물건을 훔칠 때:
  • dp[i][b + B의 흔적] = min(dp[i][b + B의 흔적], dp[i-1][b])

최종값:

• 모든 물건을 탐색한 후 dp[info.length][b] 중에서 b < m인 경우의 최소값을 반환
• 만약 모든 경우에서 b >= m이면 -1을 반환

class Solution {
    int[][] dp;

    public int solution(int[][] info, int n, int m) {
        dp = new int[info.length + 1][m];

        // 초기화
        for (int i = 1; i <= info.length; i++) {
            Arrays.fill(dp[i], n);
        }
        dp[0][0] = 0;

        // DP 수행
        for (int i = 1; i <= info.length; 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 answer = n;
        for (int j = 0; j < m; j++) {
            answer = Math.min(answer, dp[info.length][j]);
        }

        return answer >= n ? -1 : answer;
    }
}

---

✅ 결론

1. 첫 번째 시도 (Greedy - 내림차순 정렬): 간단하지만 최적해를 보장하지 않음
2. 두 번째 시도 (혼합 정렬): 경우를 나눠 탐색하지만 여전히 최적해는 아님
3. 세 번째 시도 (DP):
   • 제한 조건은 B도둑의 흔적 합을 인덱스로 사용
   • 최적화 목표는 A도둑의 최소 흔적 합을 배열의 값으로 저장
   • 모든 테스트 케이스 통과 가능 ✅

---