[백준 - 20555번] 타자연습 - Java

문제 링크

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

문제

티어: 골드 1
알고리즘: dp
민규와 명진이는 타자연습 대결을 하고 있다. 타자연습은 $N$개의 단어들로 이루어져 있으며, 각 단어는 알파벳 대문자 A부터 D까지로만 이루어져 있다. 단어의 첫 글자부터 시작해 현재 위치의 글자에 해당하는 정확한 글자를 입력하면 다음 글자로 넘어가며, 모든 글자를 입력했다면 엔터 키를 눌러 다음 단어로 넘어가는 방식이다. 이 프로그램은 오타에 관대하기 때문에, 잘못된 글자를 입력하면 패널티 없이 무시되기만 한다. 즉, 단어들을 수열로 보았을 때 타자연습에 주어진 단어가 입력한 글자들을 모은 단어의 부분 수열인 경우 단어를 입력하는 데에 성공하는 것이다.

민규는 실력이 부족해 명진이를 이길 수 없자, 꼼수를 쓰기로 했다. 프로그램이 허술해 붙여넣기가 가능한 것을 발견한 민규는 하나의 단어만을 만들어, 계속 붙여넣는 것으로 모든 단어들을 순식간에 통과하려고 한다. 즉, 민규의 단어는 단어들을 수열로 보았을 때 $N$개의 단어들을 모두 부분 수열로 가져야 한다. 이 때, 민규는 타자 속도가 느리므로 그 단어의 길이를 최소로 하고 싶다. 민규를 위해 사용할 단어를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에 단어의 수 $N$이 주어진다. $(1 \leq N \leq 6)$ 

이후 $N$개의 줄에 걸쳐 타자연습 단어를 나타내는 문자열 $S_i$가 주어진다. $S_i$는 대문자 A, B, C, D로만 이루어져 있으며 길이는 $9$ 이하이다.

출력

첫 번째 줄에 사용할 문자열을 출력한다. 단, 가능한 문자열이 여럿 있을 경우 사전순으로 최소인 것을 출력해야 한다.

풀이

가능한 문자열을 출력해야 하는데 가능한 문자열이 있다면, 길이가 적은 순으로, 길이가 같다면 사전순으로 앞선 문자열을 출력해야 한다.

dp의 각 상태는 어렵지 않다. 다음번 채워줘야 될 글자가 완전히 동일하다면, 그것이 하나의 상태가 된다.

예를 들어 예제 입력 1을 보면,

5
AACABBA
BACBA
DDDBBACB
CCCCBABD
DDDDDDD

여기서
1. 첫 번째 문자열은 3 번째부터
2. 두 번째 문자열은 2 번째부터
3. 셋 번째 문자열은 1 번째부터
4. 네 번째 문자열은 2 번째부터
5. 다섯 번째 문자열은 3 번째부터

채워줘야 한다면, 그러한 상태는 단 하나만 존재한다고 정의했을 때 중복 탐색을 없애줄 수 있다.

그러면 그러한 여러 상태 중 어떠한 상태가 와야될까?

이는 문제에 우선적인 조건을 갖춘 상태가 와야된다.
길이가 짧으면, 같다면 사전순으로 앞선 문자열이 최적의 상태가 된다.

이를 토대로 dp는 6차원 배열로 정의될 수 있다. N은 최대 6이기 때문이다.

각 차원의 index는 해당 문자열의 cursor가 된다.

그래서 dp[2][1][0][1][2][0]는 다음번 채워야 될 문자 위치가 차례대로 3, 2, 1, 2, 3임을 의미한다.

이 풀이의 시간 복잡도는 O(9^N)이지만, 문자열을 합치거나 비교하는 과정이 추가되어 훨씬 클 것이다. 하지만 시간 제한은 충분하기 때문에 가능한 풀이다.

소스 코드

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

public class Main {
    static final char[] dw = {'A', 'B', 'C', 'D'};
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      String[] words = new String[N];
      for(int i=0; i<N; i++) {
          words[i] = " " + br.readLine();
      }
      
      String[][][][][][] dp = new String[10][10][10][10][10][10]; //[현재 cursor의 위치] cursor는 마지막으로 채워진 위치를 기반
      dp[0][0][0][0][0][0] = "";
      for(int on=0; on<=9; on++) {
          for(int tw=0; tw<=9; tw++) {
              for(int th=0; th<=9; th++) {
                  for(int fo=0; fo<=9; fo++) {
                      for(int fi=0; fi<=9; fi++) {
                          for(int si=0; si<=9; si++) {
                              String str = dp[on][tw][th][fo][fi][si];
                              if(str != null) {
                                  //값이 있다면
                                  int[] indArr = {on, tw, th, fo, fi, si};
                                  fillDp(dp[on][tw][th][fo][fi][si], words, indArr, dp);
                              }
                          }
                      }
                  }
              }
          }
      }
      int[] answerInd = new int[6];
      for(int i=0; i<N; i++) {
          answerInd[i] = words[i].length() - 1;
      }
      
      System.out.println(dp[answerInd[0]][answerInd[1]][answerInd[2]][answerInd[3]][answerInd[4]][answerInd[5]]);
  }
  
  static void fillDp(String str, String[] words, int[] indArr, String[][][][][][] dp) {
      for(int i=0; i<dw.length; i++) {
          int[] newIndArr = {indArr[0], indArr[1], indArr[2], indArr[3], indArr[4], indArr[5]};
          
          //newStr이 어디까지 만족시키는지 검사.
          boolean next = false;
          for(int j=0; j<N; j++) {
              if((indArr[j] < words[j].length() - 1) && (words[j].charAt(indArr[j] + 1) == dw[i])) {
                  //새로 추가된 문자가 다음을 만족한다면
                  if(!next) {
                      next = true;
                  }
                  newIndArr[j] += 1;
              }
          }
          
          if(next) {
              //새로운 경우의 수가 가능하다면
              String newStr = str + dw[i];
              String exiStr = dp[newIndArr[0]][newIndArr[1]][newIndArr[2]][newIndArr[3]][newIndArr[4]][newIndArr[5]];
              if(exiStr == null || (newStr.length() < exiStr.length())) {
                  //null이거나 새로운 문자열의 길이가 더 작다면
                  dp[newIndArr[0]][newIndArr[1]][newIndArr[2]][newIndArr[3]][newIndArr[4]][newIndArr[5]] = newStr;
              } else if(newStr.length() == exiStr.length()) {
                  //길이가 같다면 사전 순으로 앞선 문자열이 들어가야 됨.
                  if(newStr.compareTo(exiStr) < 0) {
                      //newStr이 사전 순으로 앞선다면
                      dp[newIndArr[0]][newIndArr[1]][newIndArr[2]][newIndArr[3]][newIndArr[4]][newIndArr[5]] = newStr;
                  }
              }
          }
      }
  }
}