BOJ 1663 - XYZ 문자열

BOJ 1663 - XYZ 문자열

금방 $s(i)=s(i-3)+s(i-2)$ 꼴로 나타나는 것이 보여서 쉽게 풀었다.

$1,3$번 문제는 이 점화식 그대로 DP로 풀어주면 되고 $2$ 번 문제는 재귀를 돌려준다.

현재 $i$ 번째 레벨에서 $k$ 번째 수라면 $i-3$ 번째 레벨의 길이와 $i-2$ 번째 레벨의 길이 중 $k$가 속하는 곳으로 계속해서 파고드는 방식으로 구현하면 된다.

int len[101], xc[101], yc[101], zc[101];

void solve() {
   vi len(101);
   len[1] = 1;
   len[2] = 2;
   len[3] = 2;
   len[4] = 3;
   xc[1] = 1;
   for (int i = 5; i <= 100; i++) len[i] = len[i - 3] + len[i - 2];

   yc[2] = zc[2] = 1;
   xc[3] = zc[3] = 1;
   xc[4] = yc[4] = zc[4] = 1;
   for (int i = 5; i <= 100; i++) {
      xc[i] = xc[i - 3] + xc[i - 2];
      yc[i] = yc[i - 3] + yc[i - 2];
      zc[i] = zc[i - 3] + zc[i - 2];
   }

   debug(len);
   int p;
   cin >> p;
   if (p == 1) {
      int x;
      cin >> x;
      cout << len[x];
   } else if (p == 2) {
      int x, k;
      cin >> x >> k;
      char ans = '?';
      function<void(int, int, int)> fn = [&](int lv, int l, int r) -> void {
         if (lv == 1) {
            ans = 'X';
            return;
         }
         if (lv == 2) {
            ans = "YZ"[k - 1];
            return;
         }
         if (lv == 3) {
            ans = "ZX"[k - 1];
            return;
         }
         if (lv == 4) {
            ans = "XYZ"[k - 1];
            return;
         }
         int prefix = len[lv - 3];
         int suffix = len[lv - 2];
         if (k <= prefix) {
            fn(lv - 3, l, l + len[lv - 3] - 1);
         } else {
            k -= prefix;
            fn(lv - 2, l + prefix, r);
         }
      };
      fn(x, 1, len[x]);
      cout << ans;
   } else {
      int k;
      cin >> k;
      string t;
      cin >> t;
      if (t == "X") cout << xc[k];
      if (t == "Y") cout << yc[k];
      if (t == "Z") cout << zc[k];
   }
}