[백준 - 15822번] Ah-Choo! - Java

문제 링크

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

문제

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

링크 확인

입력

입력의 첫 줄에는 파형의 길이를 나타내는 자연수 N이 주어진다. 두 번째 줄에는 첫 파형 X의 시간 별 높이를 나타내는 N개의 정수가 공백으로 구분되어 시간순으로 주어진다. 세 번째 줄에는 두 번째 파형 Y의 시간 별 높이가 같은 형식으로 주어진다.

모든 파형의 높이는 0이상 1,000이하의 정수다.

1 ≤ N ≤ 2,000

출력

두 파형의 최소 거리를 정수로 출력한다.

풀이

두 파형의 최소 거리를 구해야 한다.
이 문제는 dp를 활용해서 풀 수 있다.

수열 X:[10, 20, 45, 20, 14, 15]
수열 Y:[10, 25, 50, 50, 30, 15]

이렇게 두 수열이 있을 때
1. 수열 X에 첫 번째부터 수열 Y에 대응 시켜보자, (X[1])
X[1]은 Y[1] ~ Y[6]까지 대응시킬 수 있다. 그런데 교차가 안되기 때문에 X[1]과 Y[3]이 대응된다면 X[1]은 Y[1], Y[2]와도 대응되어야 한다.

2. 수열 X에 두 번째를 수열 Y에 대응시키면 (X[2])
   X[2] 또한 Y[1] ~ Y[6]까지 대응시킬 수 있다. 그런데 X[1]을 먼저 대응시켜야 X[2]를 결정할 수 있는데 이미 X[1]에서 대응할 수 있는 모든 경우를 구했기 때문에 중복 탐색을 방지할 수 있다.
   예를 들어 X[2]에서 Y[2]를 대응시키려면

• X[1]과 Y[2]를 대응하는 경우 + (X[2] - Y[2])^2
• X[1]과 Y[1]를 대응하는 경우 + (X[2] - Y[2])^2
• X[2]와 Y[1]를 대응하는 경우 + (X[2] - Y[2])^2
  이렇게 세 가지 경우를 구해서 가장 작은 값을 넣어주면 된다.

내가 헷갈렸던 것은
X[1]에서 Y[2]를 대응하는 경우를 보면
어차피 Y[2]를 X[2]와 대응시키는데 X[1]에서 중복으로 대응하면 당연히 더 큰 값이라고 생각했고, 이 경우를 배제했다.

그런데 잘 생각해보면, X[1]이 Y[2]와 대응됐다는 것은 X[1]이 Y[1]을 대응하지 않는 경우(X[1] 앞에 하나의 수가 더 있다고 가정했을 때)를 포함한다. 그렇기 때문에 꼭 이 경우를 포함해서 계산해줘야 한다. (각각의 상태가 어떤 의미인지 고민해 보는 습관이 중요한 것 같다.)

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

소스 코드

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

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[] A = new int[N + 1];
      int[] B = new int[N + 1];
      init(new StringTokenizer(br.readLine()), A);
      init(new StringTokenizer(br.readLine()), B);
      int[][] dp = new int[N + 1][N + 1];
      for(int i=1; i<=N; i++) {
          int v  = (A[1] - B[i]) * (A[1] - B[i]);
          dp[1][i] = dp[1][i - 1] + v;
      }
      
      for(int i=2; i<=N; i++) {
          dp[i][1] = dp[i - 1][1] + (A[i] - B[1]) * (A[i] - B[1]);
          for(int j=2; j<=N; j++) {
              int v = (A[i] - B[j]) * (A[i] - B[j]);
              dp[i][j] = dp[i][j - 1] + v;
              dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + v);
              dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + v);
              
          }
      }
      System.out.println(dp[N][N]);
  }
  
  static void init(StringTokenizer st, int[] arr) {
      for(int i=1; i<=N; i++) {
          arr[i] = Integer.parseInt(st.nextToken());
      }
  }
}