BOJ/백준-9625-python

문제

풀이

DP	A	B
첫번째	0	1
두번째	1	1
세번째	1	2
네번째	2	3
다섯번째	3	5
여섯번째	5	8

• 위 테이블을 보면 수가 A와 B 둘 다 d[i] = d[i-1] + d[i-2] 점화식 규칙에 해당하는걸 확인할 수 있다.
• DP를 구현하기 위해 dp 테이블을 초기화하였으며, bottom-up 반복문형태로 구현하였다.
• 위 점화식 규칙을 코드로 구현하면 아래와 같다.

코드

# https://www.acmicpc.net/problem/9625
# boj, 9625: BABBA, python3
import sys

input = sys.stdin.readline

def dp(k):
    # DP 테이블 초기화
    d_a = [0] * 46
    d_b = [0] * 46

    d_a[1], d_b[1] = 0, 1
    d_a[2], d_b[2] = 1, 1

    # DP bottom-up
    for i in range(3, k+1):
        d_a[i] = d_a[i-1] + d_a[i-2]
        d_b[i] = d_b[i-1] + d_b[i-2]

    return d_a[k], d_b[k]

if __name__ == '__main__':
    k = int(input())

    print(*dp(k))

결과

출처 & 깃허브

BOJ 9625
github