[백준 - 30828번] 셰프 건공이 - Java

문제 링크

https://www.acmicpc.net/problem/30828

문제

티어: 골드 1
알고리즘: dp

알고 있었는가, 사실 건공이는 굉장히 유능한 요리사라는 사실을. 건공이는 어떤 재료들을 받아도 가장 맛있는 음식을 만들어 낼 수 있는 엄청난 능력이 있다.

건공이는 $1$번 재료부터 $N$번 재료까지 총 $N$개의 재료를 가지고 있다. 각 재료는 $T_i$의 맛 수치를 가진다. 건공이가 만드는 음식의 맛은 (사용한 모든 재료의 맛들을 XOR한 값 + 사용한 모든 재료의 개수)로 나타낼 수 있다.

$Q$개의 쿼리가 주어지고 각 쿼리마다 $l$과 $r$이 주어질 때, 각 쿼리에 대하여 $l$번째 재료부터 $r$번째 재료까지 ($r - l + 1$)개의 재료 중 $0$개 이상을 적절히 사용하여 만들 수 있는 요리의 맛 중 최댓값을 구하여라.

입력

첫 번째 줄에 재료의 개수 $N$이 주어진다. ($ 1 \leq N \leq 500$)

두 번째 줄에
$N$개의 재료의 맛 수치 $T_1, T_2, \cdots, T_N$이 공백으로 구분되어 주어진다. ($0 \leq T_i \leq 511$)

세 번째 줄에 쿼리의 개수 $Q$가 주어진다. ($1 \leq Q \leq 100\ 000$)

다음 $Q$개의 줄에 $l$과 $r$이 공백으로 구분되어 주어진다. ($1\leq l \leq r \leq N$)

출력

$Q$개의 줄에 각 쿼리마다 건공이가 만들 수 있는 요리의 맛 중 최댓값을 한 줄씩 출력한다.

풀이

건공이가 만들 수 있는 요리의 맛 중 최댓값을 한 줄씩 출력해야 한다.

요리는 여러 재료로 만들어 진다. 그래서 각 재료는 요리에 들어가거나 들어가지 않는다.

단순 브루트 포스 방식은 시간 초과가 발생하기 때문에 중복을 줄여야 한다.

만약, 1 ~ 5번째 범위에서 재료를 0개 이상 선택하고, 그 재료들을 xor한 값이 같다면, 재료의 개수가 많은 것이 최적해가 된다. 왜냐하면 선택한 재료의 개수가 맛에 +되기 때문이다.

그러면 범위는 왼쪽 인덱스, 오른쪽 인덱스로 표현할 수 있는데, xor은 어떻게 표현해야될까? 정확히는 xor의 최댓값은 몇일까? Ti의 최댓값은 511이고, 이를 이진수로 표현하면 111111111이다. 즉, 최댓값은 511이기 때문에 dp는 다음과 같이 정의된다.

dp[left][right][511]

그래서 dp[2][4][15]는 2 번재부터 4 번째까지 재료를 선택해 요리를 만들었을 때 xor 값이 15이면서, 선택할 수 있는 재료의 최대 개수가 된다.

dp[2][4]를 구할 때는 dp[2][3]에서 모든 xor 값을 돌면서, 현재 재료를 선택했을 경우와 선택하지 않았을 경우를 적용해 dp[2][4]를 채워나간다.

이러한 방식으로 채우면 중복없이 모든 경우를 최적해로 유지해 줄 수 있다.

만약 4, 8구간에서 최댓값을 출력하라고 한다면, dp[4][8]에서 모든 xor를 돌면서, xor이 존재할 때 xor값 + dp[4][8][xor값]이 가장 큰 값을 출력하면 된다.

이 풀이의 시간 복잡도는 O(N^2 x 511)이다.

소스 코드

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

public class Main {
    static int N, Q;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      int[] arr = new int[N + 1];
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=1; i<=N; i++) {
          arr[i] = Integer.parseInt(st.nextToken());
      }
      int[][][] dp = new int[N + 1][N + 1][511 + 1];
      init(dp); // -1로 초기화
      for(int l=1; l<=N; l++) {
          dp[l][l - 1][0] = 0;
          for(int r=l; r<=N; r++) {
              for(int t=0; t<=511; t++) {
                  if(dp[l][r - 1][t] != -1) {
                      //값이 존재한다면
                      //현재 재료를 선택하는 경우와 그렇지 않은 경우로 나눠진다.
                      
                      //선택한 경우
                      int sv = t ^ arr[r]; //xor한 값
                      dp[l][r][sv] = Math.max(dp[l][r][sv], dp[l][r - 1][t] + 1); //재료를 선택했기 때문에 +1
                      
                      //선택하지 않은 경우
                      dp[l][r][t] = Math.max(dp[l][r][t], dp[l][r - 1][t]);
                  }
              }
          }
      }
      
      StringBuilder sb = new StringBuilder();
      Q = Integer.parseInt(br.readLine());
      for(int i=0; i<Q; i++) {
          StringTokenizer st2 = new StringTokenizer(br.readLine());
          int l = Integer.parseInt(st2.nextToken());
          int r = Integer.parseInt(st2.nextToken());
          int answer = -1;
          for(int t=0; t<=511; t++) {
              if(dp[l][r][t] != -1) {
                  answer = Math.max(answer, t + dp[l][r][t]);
              }
          }
          sb.append(answer).append("\n");
      }
      System.out.println(sb.toString().trim());
  }
  
  static void init(int[][][] dp) {
      for(int i=0; i<dp.length; i++) {
          for(int j=0; j<dp[i].length; j++) {
              for(int k=0; k<dp[i][j].length; k++) {
                  dp[i][j][k] = -1;
              }
          }
      }
  }
}