백준 1663, XYZ 문자열

개요

문제 링크
골드 1, DP
매 단계 X->YZ, Y->Z, Z->X로 변형이 일어날 때 전체 길이 / 문자 개수 / k번째 문자 구하기

---

접근

1. 규칙성을 찾으면 크게 어렵지 않다. 우선 X,Y,Z의 개수를 생각해보자. X는 Z에서 온다. Y는 X에서 온다. Z는 X,Y에서 온다. 온다는게 뭔 말이냐 하니, 변화의 이전단계를 생각해보자. 변화를 역으로 취해보면 알 수 있다. 따라서

   X[i] = Z[i-1], Y[i] = X[i-1], Z[i] = X[i-1]+Y[i-1]

   이게 성립한다. 문자열의 길이는 X[i]+Y[i]+Z[i]이니까 따로 생각할 필요는 없다.

2. 어려운 부분은 K번째 문자 구하기이다. 문제를 잘 들여다보면 s[n]+s[n+1] = s[n+3]임을 알 수 있다. 왜냐? X는 세 번의 시행 뒤 XYZ가 된다. Y는 세 번의 시행 뒤 YZ가 된다. Z는 ZX가 된다.

   // 현재+시행
   X -> X+YZ, Y -> Y+Z, Z -> Z+X
   // 3번 시행
   X -> XYZ, Y -> YZ, Z -> ZX

   3번 시행한 결과와, 현재값 + 1번 시행한 결과가 같기 때문이다. 이걸 바탕으로 K번째 문자를 쉽게 구해줄 수 있다.

3. 만약 k가 len[n-3] = n-3번째 문자열의 길이보다 크다면, 우리는 n-2번째 문자열의 k-len[n-3] 번째 문자를 구해야 한다. 그렇지 않다면 n-3번째 문자열의 k번째 문자를 구해주면 된다. 이게 뭔 말이냐,

   // n = 6
   // s[n] = ZXXYZ
   len[4] = 3, len[3] = 2 // XYZ, ZX
   
   // 1) k=3
   // ZXXYZ
   // __O__ 이 위치 -> s[4]의 1번 위치
   answer = s[4][1] = s[n-2][k-len[n-3]]
   
   // 2) k=2
   // ZXXYZ
   // _O___ s[3]의 2번 위치
   answer = s[3][2] = s[n-3][k]

   그래서 n이 3보다 큰 동안 위 작업을 계속 반복해주면 된다. 그 뒤에는 직접 문자열을 구해 문자를 찾아주면 된다.

---

Pseudo code

// 개수
x[1] = 1, y[1] = 0, z[1] = 0
for (i = 2~n)
    {x,y,z} = {z,x,x+y}
if (q==1) return x[n]+y[n]+z[n]
if (q==3) return input[n]
if (q==2)
    while (3 < n)
        if (len[n-3] < k)
            n -= 2, k -= len[n-3]
        else
            n -= 3
    // s[n] = s[n-2]+s[n-3]
    s = "Y", t = "Z", u = "X"
    while (--n)
        {s,t,u} = {t,u,s+t}
    return u[k-1]

---

Source code

#include <iostream>
using namespace std;

using ld = long long;
int main() {
    ld q, n, k;
    char a;
    cin >> q >> n;
    if (q==2) cin >> k;
    if (q==3) cin >> a;

    ld x[n+1],y[n+1],z[n+1];
    x[1]=1,y[1]=0,z[1]=0;
    for (int i=2; i<=n; i++)
        x[i]=z[i-1],y[i]=x[i-1],z[i]=x[i-1]+y[i-1];
    if (q==1) cout << x[n]+y[n]+z[n];
    if (q==3) cout << (a=='X'?x:a=='Y'?y:z)[n];
    if (q==2) {
        while (3<n) {
            ld n2=x[n-3]+y[n-3]+z[n-3];
            if (k<=n2) n-=3;
            else
                n-=2, k-=n2;
        }
        string s,t,u,v;
        s="Y",t="Z",u="X";
        while(--n)
            v=u,u=s+t,s=t,t=v;
        cout << u[k-1];
    }
}