[백준 1904] 01타일

0. 제목

• 백준 1904 01타일
• BOJ 1904 01타일
• 파이썬 1904 01타일
• Python 1904 01타일

---

1. 문제

www.acmicpc.net/problem/1904

1904번: 01타일

---

2. 풀이

• dp[1] -> 0 -> 1개
• dp[2] -> 00, 11 -> 2개
• dp[3] -> 001, 100, 111 -> 3개 -> dp[2]에서 가장 뒤에 1추가 + dp[1]에서 가장 뒤에 00 추가
• dp[4] -> dp[3]에서 가장 뒤에 1추가 + dp[2]에서 가장 뒤에 00 추가
• dp[5] -> dp[4]에서 가장 뒤에 1추가 + dp[3]에서 가장 뒤에 00 추가
• dp[n] -> dp[n-1]에서 가장 뒤에 1추가 + dp[n-2]에서 가장 뒤에 00 추가 ➡ dp[n] = dp[n-1] + dp[n-2]
• 수가 너무 커지기 때문에 마지막에 15746으로 나눈 나머지를 출력하면 안되고 반복문 루프마다 15746으로 나눈 나머지를 구한다.

---

3. 코드

n = int(input())
 
dp = [0] * 1000001
 
dp[1] = 1
dp[2] = 2
 
for i in range(3, n + 1):
    dp[i] = (dp[i - 2] + dp[i - 1]) % 15746
 
print(dp[n])
 
 

저작자표시

'Algorithm (Python) > DP' 카테고리의 다른 글

[백준 1495] 기타리스트  (0)	2020.09.13
[백준 9251] LCS  (0)	2020.09.12
[백준 11053] 가장 긴 증가하는 부분 수열  (0)	2020.09.12
[백준 12865] 평범한 배낭  (0)	2020.09.11
[백준 1904] 01타일  (0)	2020.09.10