[백준] 1904 01타일 with Python

📌 BOJ 1904 01타일

💡 조건

1. 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

2. 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다.
   결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

3. N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.)
   또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

4. N이 주어진다.
   (1 ≤ N ≤ 1,000,000)

5. 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

6. DP 유형의 문제

🖥 소스 코드

from sys import stdin

n = int(stdin.readline())
dp = [0 for _ in range(1000001)]
dp[1], dp[2], dp[3], dp[4] = 1, 2, 3, 5

for i in range(5, n + 1):
    num = ((dp[i-1] + dp[i-2]) % 15746)
    dp[i] = num

print(dp[n])

🔖 예제 및 실행결과

예제

4

실행결과

5

⌨️ 문제 풀이

1. N이 100만까지 들어올 수 있다. 그러므로, DP 리스트의 크기는 1000001 이 되어야한다.

2. N의 값이 3일 때까지 직접 계산을 해보면 dp[3] 까지의 값은 아래와 같다.

   • 1, 2, 3

3. dp[i] = (dp[i-1] + dp[i-2]) % 15746
   위와 같은 점화식을 만들 수 있다.

💾 느낀점

1. 다이나믹프로그래밍을 이용해 문제를 풀이할 수 있는 문제였습니다.
2. 다른 DP 문제와 다르게 친절하고, 쉽고 재미있었습니다.