[백준/1663] XYZ 문자열 (Python)

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

1663번: XYZ 문자열

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:23:36

 

---

 

문제 설명

 

"XYZ 문자열"이란 아래와 같은 문법에 의해 단계별로 만들어지는 일련의 문자열들을 뜻한다.

 

• "XYZ 문자열"은 세 개의 문자 X, Y, Z로만 이루어진다.
• 1단계 "XYZ 문자열"은 X로 시작한다.
• 다음 단계의 "XYZ 문자열"은 바로 이전 단계의 "XYZ 문자열"에서 아래와 같은 규칙에 따라 변형되어 만들어진다.
  • X는 YZ로 변형된다.
  • Y는 Z로 변형된다.
  • Z는 X로 변형된다.

위와 같은 문법에 따라 1단계부터 몇 단계의 "XYZ 문자열"을 차례로 적어 보면 아래와 같다.

 

1. X
2. YZ
3. ZX
4. XYZ
5. YZZX
6. ZXXYZ

N단계의 "XYZ 문자열"과 관련해서, 아래의 문제 중 하나를 푸는 프로그램을 작성하시오.

 

1. N단계의 XYZ 문자열의 길이를 구한다.
2. N단계의 XYZ 문자열에서 k번째 문자가 무엇인지 구한다.
3. N단계의 XYZ 문자열에서 특정한 문자가 몇 번 나타나는지 구한다.

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

2
5
1

 

출력 예시

 

Y

 

 

---

 

풀이

 

x, y, z의 개수를 저장하는 DP를 풀이해보도록 하자. N > 3일때, N번째의 문자열은 N-3번째 문자열 + N-2번째 문자열임을 쉽게 눈치챌 수 있다. 즉 O(N) 시간복잡도 내에 모든 DP값을 계산할 수 있다.

 

다음은 문제를 풀어보자. 1번 문제는 DP[N]의 sum값, 3번 문제는 DP[N]의 그 문자에 해당하는 값을 출력해주면 된다. 2번 문제 역시 재귀적으로 풀 수 있는데, 만약 index가 DP[N-3]의 합보다 작거나 같다면 DP[N-3]에서 조사를 할 수 있고, 그렇지 않다면 idx를 idx - sum(DP[N-3])값으로 업데이트 후 DP[N-2]에서 조사를 이어나갈 수 있겠다. 1 <= N <= 3인 경우만을 매핑해주면 된다. 이 역시 재귀적으로 풀이 가능하다.

 

풀이 코드

N = 100
dp = [[0]*3 for _ in range(N+1)]
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 1]
dp[3] = [1, 0, 1]

for i in range(4, N+1) :
  for j in range(3) :
    dp[i][j] += dp[i-2][j] + dp[i-3][j]

ptype = int(input())
num = int(input())

if ptype == 1 :
  print(sum(dp[num]))
elif ptype == 2 :
  idx = int(input())
  while num >= 4 :
    if sum(dp[num-3]) >= idx :
      num -= 3
    else :
      idx -= sum(dp[num-3])
      num -= 2
  if num == idx == 1 or num == 3 and idx == 2 :
    print('X')
  elif num == 2 and idx == 1 :
    print('Y')
  else :
    print('Z')
else :
  idx = ord(input()) - ord('X')
  print(dp[num][idx])

풀이 완료!