[코드트리] 2명의 도둑

문제

---

Codetree | Learning to Code with Confidence

 

알고리즘 [접근 방법]

---

이 문제는 완전탐색 + 부분 조합 최적화 문제로 파악했다

내가 처음 접근했을 때는
두 도둑이니까 DFS를 두 번 돌려야 하는건가
각 도둑의 선택 구간에서 부분집합을 또 만들어야 하는지? 등
이런 식으로 고민했는데, 구현 자체는 의외로 단순했다.

핵심 포인트는 두 가지다.

1. 도둑 A가 고를 수 있는 모든 구간을 탐색
2. 도둑 B는 A 구간을 침범하지 않는 곳에서 다시 고르기

그리고 각각의 구간에서는

“M개의 물건 중 일부를 골라 총 무게 ≤ C 를 만족하면서 가치(무게²) 최대화”
라는 배낭문제를 풀어야 하는데,
M이 최대 5 수준이라서 굳이 DP를 쓰지 않아도 “정렬 후 그리디”로 해결 가능했다.

 

사실 정석은 부분집합 전부 탐색(2^M) 인데, 내가 짠 방식처럼
오름차순 정렬 → 작은 것부터 담기
해도 충분히 정답 처리가 된다.

 

그리고 두 도둑이 한 행에서 겹치지 않도록 하기 위해
같은 행일 경우 y + M ≤ next start 조건을 강제로 뛰어넘는 로직을 넣었다.
이게 없으면 중복 탐색이 터져서 시간이 많이 낭비된다.

 

 

풀이

---

import java.util.*;
import java.io.*;

public class Main {
    static int N, M, C, max = Integer.MIN_VALUE;
    static int[] arr =  new int[2];
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[N][N];

        for(int x = 0; x < N; x++){
            st = new StringTokenizer(br.readLine());
            for(int y = 0; y < N; y++)
                map[x][y] = Integer.parseInt(st.nextToken());
        }

        dfs(0,0,0);
        System.out.println(max);
    }
    // 두 도둑이 집는 함수
    public static void dfs(int nx, int ny, int n) {
        // 두 도둑이니까 dfs 2번일까?
        if(n == 2) {
            int sum = 0;
            for(int i = 0; i < 2; i++) sum += arr[i];
            if(max < sum) max = sum;
            return;
        }

        // 완전 탐색으로 지정. 단, 열은 N-M까지 이동
        for(int x = nx; x < N; x++){
            for(int y = 0; y <= N-M; y++){
                if(y == 0 && x == nx && ny + M <= N-M) y = ny + M; // 같은 행일때 중복 제거
                arr[n]= calc(x, y);
                dfs(x, y, n+1);
            }
        }
    }

    // 가치 계산 함수
    // 주어진 좌표에서 M행까지 담아야 하는데 크기 순으로 담는 것이 좋아보임.
    // 정렬을 하고 하나씩 탐색하며 크기가 초과하지 않을때까지 담기
    // 만약 c가 0이되면 바로 return
    public static int calc(int x, int y){
        int c = C,
            sum = 0;
        int[] temp = new int[M];

        // 값 복사
        for(int m = 0; m < M; m++)
            temp[m] = map[x][y+m];

        Arrays.sort(temp);
        for(int i = 0; i < M; i++){
            if(temp[i] <= c) {
                sum += (int)Math.pow(temp[i], 2);
                c -= temp[i];
            }
        }

        return sum;
    }
}

class Location {
    int x;
    int y;
    int cost;
    public Location(int x, int y, int cost) {
        this.x = x;
        this.y = y;
        this.cost = cost;
    }
}

// 가방에 최대한 가치가 높은 물건들을 담는다
// 물건의 가치는 무게^2 이다.

 

 

정리

---

이 문제에서 중요한 부분은 “도둑 두 명의 선택 범위가 겹치지 않게 순회하는 방식”이었다.
그걸 해결하니까 나머지는 그냥 브루트포스 + 간단한 최적화로 끝났다.

사실 더 깔끔한 방법은 각 구간의 부분집합 가치(2^M)를 미리 계산해 DP 테이블처럼 저장해두는 방식인데 M이 작다 보니 정렬 후 greedy만으로도 충분했다