[Python3] 백준 1904번 01타일

사용 언어 - Python3

1904번: 01타일

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이

www.acmicpc.net

1. dp = [0]*(1000001), n+1 만큼 0으로 이루어진 리스트 dp 생성

2. 예외처리

n이 1,2이면, 답이 정해져있다. 가독성을 위해 인덱싱은 1부터 한다.

dp[1] = 1

dp[2] = 2

3. n이 3이상인 경우

dp[i] = i까지의 최대값

dp[i]=(dp[i-2]+d[i-1])%15746

dp[n] = 모든 2진 수열의 개수를 15746으로 나눈 나머지 <-- 정답

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])

[백준] 1904번 01타일 파이썬 해설

출처 : https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱

sungmin-joo.tistory.com

GitHub - yyeongeun/codingtest: 코딩테스트 공부

코딩테스트 공부. Contribute to yyeongeun/codingtest development by creating an account on GitHub.

github.com