[백준 1663 / Python] XYZ 문자열

XYZ 문자열

🔍 알고리즘 분류

• DP

💡 문제 풀이

단계가 4이상일 때 문자열이 만들어지는 규칙
➡️ 3번째 전 문자열 + 2번째 전 문자열

• 1번 문제
  - 문자열의 길이를 담는 dp 배열 생성

  • dp[i] = dp[i-3] + dp[i-2]

• 2번 문제
  - 각 문자의 개수를 담는 cnt 배열 생성

  • 0-2까지 3번 반복하며 cnt[i][j] = cnt[i-3][j] + cnt[i-2][j]

• 3번 문제
  - 3단계까지 기저 문자열을 담는 base 배열 생성

  • find(idx, depth)함수로 재귀적으로 이분탐색
    • 왼쪽에서 온 경우: idx <= depth[i-3]
    • 오른쪽에서 온 경우: idx > depth[i-3]
    • depth가 3이하이면, base에서 찾아서 반환

📄 코드

t = int(input())
n = int(input())

dp = [0] * 101
cnt = [[0, 0, 0] for _ in range(101)]
base = ["", "X", "YZ", "ZX"]

dp[1] = 1
dp[2] = 2
dp[3] = 2
cnt[1] = [1, 0, 0]
cnt[2] = [0, 1, 1]
cnt[3] = [1, 0, 1]

# 이분탐색으로 기저문자 찾기
def find(idx, depth):
    if depth <= 3: # 기저문자 반환
        return base[depth][idx - 1]
    if dp[depth - 3] >= idx: # 왼쪽에서 옴
        return find(idx, depth - 3)
    else: # 오른쪽에서 옴
        return find(idx - dp[depth - 3], depth - 2)

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

if t == 1:
    print(dp[n])
elif t == 2:
    k = int(input())
    print(find(k, n))
else:
    ch = input()
    print(cnt[n][ord(ch) - ord('X')])

• 시간복잡도: O(N)

참고: https://ongveloper.tistory.com/311