[Python] 파이썬 백준(1904) 01타일

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

1904번: 01타일

---

나의 풀이

• 0과 1이 적힌 타일이 있음
• 0을 00 만 사용 가능하고 1은 단독으로 사용 가능함
• N이 주어졌을 때 만들 수 있는 모든 가짓수

1은 1 타일을 하나만 쓰는 경우, 2는  00 타일을 하나만 쓰는 경우로 경우의 수는 1로 같아 피보나치를 구하는 방법과 같은 approach를 가짐

import sys

n = int(sys.stdin.readline())
tile_list = [0]*1000000
tile_list[0], tile_list[1] = 1, 2
for i in range(1, n-1):
    tile_list[i+1] = (tile_list[i-1] + tile_list[i])%15746
print(tile_list[n-1])

---

다른 사람의 풀이

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

 

range만 다를 뿐 같은 approach를 사용함