[백준 - 2216번] 문자열과 점수 - Java

문제 링크

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

문제

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

입력

첫째 줄에 세 정수 A, B, C (0 < A ≤ 10,000, -10,000 ≤ B, C < 0) 가 주어진다. 그리고 둘째 줄에 X가, 셋째 줄에 Y가 주어진다. 각 문자열의 길이는 3,000자를 넘지 않으며 빈 문자열은 입력으로 주어지지 않는다.

출력

첫째 줄에 최대 총점을 출력한다.

풀이

최대 총점을 출력해야 한다.

이 문제는 dp를 이용해서 풀 수 있다. 계산 값이 반복되는 구조이기 때문이다.

다음과 같은 예제가 있을 때

10 -1 -5
abc
dc

X에서의 a와 Y에서의 d만 포함되는 경우의 수는 (x는 공백)

1. a와 d가 같은 위치인 경우
   a
   d,

2. a와 Y의 첫 번째 공백이 같은 위치인 경우
   ax
   xd,

3. a와 Y의 두 번째 공백이 같은 위치인 경우
   xa
   dx

이렇게 세 가지 case를 분류할 수 있다.

그리고 다음 X에서의 a와 Y에서의 d,c만 포함되는 경우의 수는

1. ax
   dc

2. xax
   dxc

3. axx
   xdc

4. xa
   dc

이렇게 네 가지로 분류가 되는데 1, 2, 3번의 경우를 잘 보면 c와 공백이 마지막에 추가되고 그 전의 3가지 case를 합한 경우임을 알 수 있다.

그래서 좀 더 일반화하면 c와 공백이 추가되는 경우와 두 문자열의 마지막 두 문자를 비교하는 경우로 나눌 수 있다. 점화식을 세우면 다음과 같다. (이해가 안간다면 바텀 업으로 더 진행해 보자)

dp[i][j] = max(dp[i-1][j] + B, dp[i][j-1] + B, dp[i-1][j-1] + (A or C));

dp를 생성하고 i가 0일 때의 모든 경우와 j가 0일 때의 모든 경우를 초기화해 줘야 한다.

예를 들어 dp[0][4]는 Y 문자열의 4개 문자가 X의 4개의 공백과 같은 위치임을 뜻하기 때문에 B * 4 값이 들어가야 한다.

이 풀이의 시간 복잡도는 O(X.length() * Y.length())다.

소스 코드

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

public class Main {
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int A = Integer.parseInt(st.nextToken()); //같을 경우
      int B = Integer.parseInt(st.nextToken()); //하나만 공백인 경우
      int C = Integer.parseInt(st.nextToken()); //두 문자가 다 다른 경우
      
      String X = br.readLine();
      String Y = br.readLine();
      
      int[][] dp = new int[X.length() + 1][Y.length() + 1];
      
      for(int i=1; i<=Y.length(); i++) {
          dp[0][i] = i * B;
      }
      
      for(int i=1; i<=X.length(); i++) {
          dp[i][0] = i * B;
      }
     
      for(int i=1; i<=X.length(); i++) {
          for(int j=1; j<=Y.length(); j++) {
              dp[i][j] = Math.max(dp[i - 1][j] + B, dp[i][j - 1] + B);
              int cv = A; //같은 경우는 그대로 사용됨
              if(X.charAt(i - 1) != Y.charAt(j - 1)) {
                  //다른 경우
                  cv = C;
              } 
              dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + cv);
          }
      }
      
      System.out.println(dp[X.length()][Y.length()]);
  }
}