[백준 - 18790번] N의 배수 (1) - Java

문제 링크

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

문제

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

$2N-1$개의 수가 주어진다. 이 중 합이 $N$으로 나누어 떨어지는 수 $N$개를 구하여라.

입력

첫째 줄에 $N$이 주어진다. ($1 \le N \le 500$)

둘째 줄에 $0$이상 $N$미만의 수 $2N-1$개가 공백으로 구분되어 주어진다.

출력

첫째 줄에, 조건을 만족하는 수 $N$개를 공백으로 구분하여 출력한다.

답을 만족하는 경우가 여럿 있는 경우, 그 중 임의의 하나를 출력하면 정답으로 인정된다. 출력하는 수들의 순서는 관계 없다.

답을 만족하는 수들이 존재하지 않는 경우 -1을 출력하여라.

풀이

2N - 1개의 수가 주어질 때 이 중 합이 N으로 나누어 떨이지는 수 N개를 구해야 한다.

단순히 가능한 모든 N개를 뽑아서 합이 N의 배수가 되는 지 확인하는 것은 시간 제한을 지킬 수 없다.

그러면 N개를 뽑는 것과 같은 동작을 효율적으로 해야하는데, 여기서 합을 생각해 볼 수 있다.
합이 같은 경우는 중복 처리를 하는 것이다.

하지만 단순히 합이 같은 경우만을 생각하면 안된다. 왜냐하면 다음 선택할 수 있는 수가 다를 수 있고, 몇 개를 골랐는지에 따라서 다를 수 있다.

그래서 합이 같으면서, 선택한 개수가 같으며 다음으로 선택할 수 있는 선택지가 같아야지 중복 처리를 할 수 있다.

예를 들어 4 번째 인덱스까지 3개를 뽑았을 때 합이 같은 수열이 여러 개라면 이를 하나로 처리하면 되는 것이다. 그 이후에 선택할 수 있는 수는 5 번재 인덱스부터이기 때문에 선택지가 다 같으며, 선택한 개수도 같기 때문이다.

이를 토대로 dp를 정의하면 dp[A][B]

• A는 뽑은 개수
• B는 합이 된다.

여기서 해결해야 될 문제가 하나 더 있다. B의 범위인데, B의 범위는 500 * 999이기 때문에 약 50만이다. 그렇다고 50만으로 dp를 정의하면 시간 복잡도나 공간 복잡도의 제한을 지키지 못한다.

그래서 50만을 줄여줘야 하는데 생각해보면,
N이 500이라 했을 때 500의 배수면 500 1000 1500..이고, 501에서 다음 배수가 되려면 499가 필요하고, 결국 501을 1로 처리해도 500의 배수를 구할 수 있다는 것을 알게된다.

그러니까 N보다 커진 합은 N을 빼면 된다. 실제 합이 1000이라고 해도 501에서 1000이 될 때가지 필요한건 결국 499이기 때문이다.

그래서 B의 범위는 N으로 줄여줄 수 있다.
A또한 뽑은 개수이기 때문에 최대 N이다.

이제 맨 앞 인덱스부터 dp를 채워준다.
4
1 2 3 0 1 2 3에서
인덱스 1부터 보면, dp[1][1]이 가능하다.
인덱스 2를 보면, dp[1][2]이 가능하고, dp[2][3]이 가능하다.

이런 방식으로 현재 인덱스에서 가능한 경우를 지금까지 구한 dp를 활용해서 구해주면 된다.

여기서 주의할 점은 dp[A][B]라고 했을 때 A가 큰 것부터 처리해야 된다.
왜냐하면 A가 1인 경우부터 처리하면 dp[2][?] 값을 추가하고, 다음 A가 2일 때 방금 추가한 dp[2][?]를 활용해서 dp[3][?]을 만들기 때문이다. 즉, 하나의 수를 여러 번 뽑는 경우가 생긴다. 이를 방지하기 위해서 A는 N-1부터 시작해야 한다.

마지막으로 처리해줘야 할 부분은 출력하고자 하는 것은 수열이기 때문에 각 인덱스에서 새로운 경우를 추가해줬을 때 연결해준 dp를 같이 저장해야 한다.

예를 들어 1 2 3의 합을 가진 dp[3][6]을 4번 째 인덱스인 5와 연결할 때
dp[4][11]에 dp[3][6]의 정보를 저장해야 한다.
그래서 역추적을 통해 dp[4][11]에서는 5, dp[3][6]에서는 3, dp[2][3]에서는 2..와 같이 합을 만들어내는 수열을 찾을 수 있게 된다.

이 풀이의 시간 복잡도는 약 O(N^3)이 된다.

소스 코드

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

class Link {
    int cur;
    Link beforeLink;
    Link(int cur, Link beforeLink) {
        this.cur = cur;
        this.beforeLink = beforeLink;
    }
}

public class Main {
    static int N;
  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[2 * N];
      StringTokenizer st = new StringTokenizer(br.readLine());
      int last = (2 * N - 1);
      for(int i=1; i<=last; i++) {
          arr[i] = Integer.parseInt(st.nextToken());
      }
      Link[][] dp = new Link[N + 1][N + 1];
      
      dp[1][arr[1]] = new Link(arr[1], null);
      for(int i=2; i <= last; i++) {
          for(int j=N-1; j>=1; j--) {
              if(i <= j) {
                  continue;
              }
              
              if((last - i) + 1 + j < N) {
                  break;
              }
              
              for(int k=0; k<=N; k++) {
                  if(dp[j][k] != null) {
                      int nSum = (k + arr[i]) > N ? (k + arr[i]) - N : (k + arr[i]);
                      if(dp[j + 1][nSum] == null) {
                          dp[j + 1][nSum] = new Link(arr[i], dp[j][k]);
                      }
                  }
              }
          }
          dp[1][arr[i]] = new Link(arr[i], null);
      }
      if(dp[N][N] == null && dp[N][0] == null) {
          System.out.println(-1);
      } else {
          StringBuilder sb = new StringBuilder();
          if(dp[N][0] != null) {
              for(int i=1; i<=N; i++) {
                  sb.append(0).append(" ");
              }
          } else {
              Link link = dp[N][N];
              for(int i=1; i<=N; i++) {
                 sb.append(link.cur).append(" ");
                 link = link.beforeLink;
                }
          }
          System.out.println(sb.toString().trim());
      }
  }
}