[DP/동적계획법] 백준 1904 01타일 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1904번: 01타일

 

 

 

2. 문제 풀이

 1과 00의 조합으로 만들 수 있는 길이가 N인 2진 수열의 개수를 구하는 문제입니다.

 

N = 1) 1 => 1개
N = 2) 11, 00 => 2개
N = 3) 111, 001, 100 => 3개
N = 4) 1111, 0011, 1001, 1000, 0000 => 5개
N = 5) 11111, 00111, 10011, 11001, 11100, 00001, 00100, 10000 => 8개

 규칙을 잘 살펴보면 마치 피보나치 수열과 같습니다. cache[N] = cache[N-2] + cache[N-1] 의 규칙성을 보입니다.

 사실 '길이가 N인 2진 수열'은 '길이가 N-2인 2진 수열의 뒤에 00을 붙인 것'과 '길이가 N-1인 2진 수열의 뒤에 1을 붙인 것'의 합과 같습니다. 그 때문에, 피보나치 수열과 같은 규칙성이 생겨납니다.

 

2022.02.14 - [Algorithm] - [DP/동적계획법] 백준 10826 피보나치 수 4 - Python

[DP/동적계획법] 백준 10826 피보나치 수 4 - Python

 

 

 

3. 코드

# 입력
N = int(input())

# DP
cache = [0] * 1000001
cache[1] = 1
cache[2] = 2

for i in range(3, N+1):
    cache[i] = (cache[i-1] + cache[i-2]) % 15746
print(cache[N])