방과후
ALGORITHM NOTE약 1분

BOJ 26607 - 시로코와 은행털기

합을 잘 모으면 곱이 커진다!

#algorithm#boj#gold#math#dp#knapsack
아카이브로 돌아가기

문제 링크

문제

블루아카이브에 있는 아비도스 고등학교 학생, 스나오오카미 시로코는 은행 터는 것을 자주 시뮬레이션한다.

게임의 마스코트, 스나오오카미 시로코이다.

어느 날, 정말로 은행을 털어보고 싶다는 생각이 든 시로코는 은행을 털 준비를 하기 시작했다. 우선, 은행 터는 것을 함께 할 팀을 만들 것인데, 경쟁을 뚫고 마지막까지 살아남은 n명 중에서 최종적으로 k명을 팀원으로 선발할 계획이다. 지원자들은 각각 힘과 스피드 수치 a, b가 주어지는데, 쟁쟁한 경쟁을 뚫고 살아남은 자들답게 a + b는 모두 동일하다.

i번째 팀원으로 선발한 사람의 능력치가 각각 aᵢ, bᵢ라 할 때, 그 팀의 종합 능력치는 (Σ aᵢ) × (Σ bᵢ)이다. 팀의 능력치를 최대화하게 지원자들을 선발하려 할 때 그때 그 팀의 능력치를 출력하라.

입력

첫 번째 줄에 사람의 수 n과 뽑을 인원 k, 그리고 힘과 스피드 수치의 합 x가 공백으로 구분되어 주어진다.

그 다음 줄부터 n개의 줄에는 각 사람들이 지닌 힘과 스피드 능력치 a, b가 주어진다.

출력

팀의 능력치를 최대화하게 인원을 선발할 때, 그 팀의 능력치를 출력하라.

풀이

핵심은 두 값이 주어져도 실제로는 하나의 합만 추적하면 된다는 점이다. 코드에서도 두 번째 값은 따로 쓰지 않고, 첫 번째 값 합만 상태로 관리한다.

정확히 K명을 뽑아 만들 수 있는 합을 모두 구해 두면 나머지 값 합은 자동으로 K * X - sum으로 정해진다. 따라서 가능한 합마다 sum * (K * X - sum)의 최댓값을 보면 된다.

코드에서는 solve(cnt, idx, sum) DFS와 visited[cnt][idx][sum] 메모이제이션으로 중복 상태를 막는다. 결국 조합 자체보다 만들 수 있는 합의 집합을 구하는 문제가 핵심이다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean[][][] visited;
    static boolean[] shiroko;
    static int[] teammate;
    static int N, K, X;
 
    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());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
 
        teammate = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            teammate[i] = Integer.parseInt(st.nextToken());
            st.nextToken(); // 값은 하나면 됨 (B = X - A)
        }
 
        shiroko = new boolean[K * X + 1];
        visited = new boolean[K + 1][N + 1][K * X + 1];
        solve(0, 0, 0);
 
        int ans = 0;
        for (int i = 0; i <= K * X; i++) {
            if (shiroko[i]) {
                ans = Math.max(ans, i * (K * X - i));
            }
        }
 
        System.out.println(ans);
    }
 
    static void solve(int cnt, int idx, int sum) {
        if (visited[cnt][idx][sum]) return;
        visited[cnt][idx][sum] = true;
 
        if (cnt >= K || idx >= N) {
            if (cnt == K) shiroko[sum] = true;
            return;
        }
 
        solve(cnt + 1, idx + 1, sum + teammate[idx]);
        solve(cnt, idx + 1, sum);
    }
}

복잡도

  • 시간 복잡도: 상태 수 기준 O(N⋅K⋅KX)O(N \cdot K \cdot KX)
  • 공간 복잡도: 방문 배열 기준 O(N⋅K⋅KX)O(N \cdot K \cdot KX)

마무리

둘 다 따로 들고 갈 필요 없이 한쪽 합만 알면 다른 쪽은 자동으로 정해진다. 선택 문제를 합의 도달 가능성 문제로 바꾸는 순간 구조가 단순해진다.