[실버 3] 백준 1904 - 01타일 (파이썬)

https://www.acmicpc.net/problem/1904

풀이

길이가 N인 이진 문자열 중 1 또는 00만 사용해서 만들 수 있는 경우의 수를 구하는 문제이다.

1 또는 00만 사용해서 N자리 수를 만들 수 있는 경우의 수 = 피보나치 수열

• 길이가 N일때 만들 수 있는 경우의 수를 D[n]이라고 할때,
  • D[N - 1] 뒤에 “1”을 붙으면 길이 N이 된다.
  • D[N - 2] 뒤에 “00”을 붙이면 길이 N이 된다.

즉 점화식은 다음과 같다.

✅ D[N] = D[N - 1] + D[N - 2]

초기값을 1, 2로 미리 초기항을 설정한다.

최대 N이 1,000.000이므로 충분히 크게 초기화 하고, 중간에 나머지 연산을 해줘야 오버플로우를 방지 할 수 있기에, 매 실행시 mod로 나머지 연산을 해준다.

시간 복잡도 분석

O(N) : 한번의 for 루프로 N까지 계산

코드

# 백준 1904 - 01타일
# 분류 : 다이나믹 프로그래밍

N = int(input())

mod = 15746

D = [0] * 1000001

D[1] = 1
D[2] = 2

for i in range(3, N + 1) :
    D[i] = D[i - 1] + D[i - 2]
    D[i] %= mod

print(D[N])