[백준 - 1663번] XYZ 문자열 - Java

문제 링크

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

문제

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

입력

첫째 줄에 문제 번호가 주어진다. 이는 1, 2, 3 중 하나이다. 이어서 둘째 줄에 자연수 N(1 ≤ N ≤ 100)이 주어진다. 문제 2인 경우는 셋째 줄에 자연수 k가, 문제 3인 경우는 셋째 줄에 X 또는 Y 또는 Z가 주어진다. k는 항상 N번째 문자열의 길이보다 작거나 같다.

출력

문제 1인 경우는 길이를 나타내는 정수를, 문제 2인 경우는 k번째 문자를, 문제 3인 경우는 특정한 문자가 나타난 횟수를 각각 첫째 줄에 출력하면 된다.

풀이

문제 1, 2, 3에 대한 답을 출력해야 한다.

가장 어려운 문제 2를 푸는 과정으로 풀이를 진행하겠다.

일단 X부터 시작해서 6까지 나열해본다.

1. X
2. YZ
3. ZX
4. X/YZ
5. YZ/ZX
6. ZX/XYZ

/로 문자열을 구분해줬을 때 규칙이 보이는가?

N이 4일 때 -> 문자열 1/문자열 2
N이 5일 때 -> 문자열 2/ 문자열 3
N이 6일 때 -> 문자열 3/ 문자열 4

이렇게 N>=4일 때 (문자열 N - 3)/(문자열 N - 2)이 반복되는 구조임을 알 수 있다.

그러면 각 1 ~ N마다 실제 XYZ 문자열을 담고 있어야 할까? XYZ의 길이는 예상컨데 int의 최대 범위보다 훨씬 클 것이다.

그래서 문자열이 아닌 다른 정보를 저장해야 한다.

만약 N이 6일 때 3 번째 문자를 찾는다고 했을 때 문자열 3과 문자열 4의 길이를 알고 있으면 찾을 수 있지 않을까?

문자열 3의 길이는 2고,
문자열 4의 길이는 3이다.
그러면 문자열 6(문자열 3/문자열 4)의 3 번째는 문자열 4의 첫 번째가 된다.

다시 문자열 4(문자열 1/ 문자열 2)의 첫 번째는 문자열 1의 첫 번째가 된다.
그래서 X를 출력하면 결과적으로 N이 6일 때 3 번째 문자의 답이 된다.

문자열 1 ~ 3까지는 길이가 짧기 때문에 저장해둘 수 있고, N부터 시작해서 문자열 1 ~ 3까지의 k가 몇 인지를 앞에 방법으로 구하면 된다.

지금까지 2번 문제 풀이였고, 이제 1, 3번 문제를 풀어야 한다.
1, 3번은 쉽다. 앞에서 찾은 규칙을 활용하면 되는데 문자열 4는 문자열 1과 문자열 2의 합이기 때문에
각 문자열의 같은 문자의 개수를 더해주면 문제 3을 풀 수 있고, 현재 문자열의 X, Y, Z 개수의 합이 곧 문제 1번의 답이 된다.

결과적으로 문제 1, 3을 풀면 문제 2에서 필요한 각 문자열의 길이를 알 수 있기 때문에 구해놓은 값(dp)으로 앞에서 풀이했던 방식을 적용하면 된다.

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

소스 코드

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

class XYZ {
    long X, Y, Z;
    int lInd, rInd; //각 문자의 개수
    
    public XYZ(long X, long Y, long Z, int lInd, int rInd) {
        this.X = X;
        this.Y = Y;
        this.Z = Z;
        this.lInd = lInd;
        this.rInd = rInd;
    }
    
    public long getLen() {
        return X + Y + Z;
    }
    
    public long getCharLen(char c) {
        if(c == 'X') {
            return X;
        } else if(c == 'Y') {
            return Y;
        }
        return Z;
    }
}

public class Main {
    static int T, N;
    static long k;
    static char c;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      T = Integer.parseInt(br.readLine());
      N = Integer.parseInt(br.readLine());
      if(T == 2) {
          k = Long.parseLong(br.readLine());
      } else if(T == 3) {
          c = br.readLine().charAt(0);
      }
      
      
      
      XYZ[] dp = new XYZ[N + 1];
      dp[1] = new XYZ(1, 0, 0, -1, -1);
      if(N >= 2) {
          dp[2] = new XYZ(0, 1, 1, -1, -1);
      }
      
      if(N >= 3) {
          dp[3] = new XYZ(1, 0, 1, -1, -1);
      }
      for(int i=3; i<N; i++) {
          int left = i - 2;
          int right = i - 1;
          dp[i + 1] = new XYZ(dp[left].X + dp[right].X,
                              dp[left].Y + dp[right].Y,
                              dp[left].Z + dp[right].Z,
                              left, 
                              right);
      }
      
      if(T == 1) {
          System.out.println(dp[N].getLen());
      } else if(T == 3) {
          System.out.println(dp[N].getCharLen(c));
      } else if(T == 2) {
          String[] strs = new String[4];
          strs[1] = "X";
          strs[2] = "YZ";
          strs[3] = "ZX";
          
          int curInd = N;
          while(curInd > 3) {
              XYZ left = dp[dp[curInd].lInd];
              XYZ right = dp[dp[curInd].rInd];
              if(k <= left.getLen()) {
                  //왼쪽 XYZ에 포함된다면
                  curInd = dp[curInd].lInd;
              } else {
                  //오른쪽 XYZ에 포함된다면
                  k = k - left.getLen();
                  curInd = dp[curInd].rInd;
              }
          }
          System.out.println(strs[curInd].charAt((int) k - 1));
      }
  }
}