백준 9625. BABBA 파이썬 풀이 (DP)

문제

백준 9625. BABBA

풀이

버튼을 K번 눌렀을 때 출력되는 문자열을 알기 위해서는 버튼을 K-1, K-2, …, 2, 1번 눌렀을 때의 문자열을 알아야 한다. 동일한 연산의 반복을 피하기 위해 Bottom-up 형태의 동적계획법을 활용할 수 있을 것이다. 버튼을 1~45회 눌렀을 때의 결과를 미리 계산해 저장해놓고 필요한 정보만을 취하면 된다.

처음에는 냅다 replace() 함수를 가지고 문자열 치환을 직접 구현한 뒤 K번째 문자열의 A, B 개수를 세어 반환하려고 했다. 그러나 그럴 필요가 없다! 이 문제에서는 문자열 전체를 요구하지 않으며, A와 B의 개수만 계산하면 된다. 구현에만 초점을 맞추면 문제를 풀 수 없어요 핵심을 봐야 돼요

K의 값에 따라 출력되는 문자열을 보면, 규칙을 찾을 수 있다.

바로 현재(K) 문자열의 A의 개수는 이전(K-1번째) 문자열의 B의 개수와 같고, 현재 B의 개수는 이전 문자열의 A+B의 개수와 같다는 규칙이다.

코드

위 규칙을 찾으면 코드 자체는 매우 간단하게 짤 수 있다. K번째 문자열의 A와 B의 개수를 저장하는 리스트 a와 b를 생성하고, K가 1~45일 때에 대해 해당 리스트를 완성한 뒤 입력 받은 K 값에 대한 a[K]와 b[K]를 출력한다.

a = []
b = []

a.append(1)
b.append(0)

for i in range(1, 46):
    a.append(b[i-1])
    b.append(a[i-1] + b[i-1])

K = int(input())
print(a[K], b[K])