Computer Science/Algorithm
[Baekjoon] DP - 1904 01타일
ddu0422
2023. 9. 20. 16:24
문제
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
풀이
"""
00 타일
1 타일
N인 모든 2진 수열을 만들 수 없다.
N = 1 => 1
N = 2 => 00, 11
N = 3 => 100, 001, 111
N = 4 => 0011, 0000, 1001, 1100, 1111
2xn 타일과 동일
0 => 2x1
1 => 1x2
"""
n = int(input())
MOD = 15746
def solution(n):
if n == 1:
return 1
a = 1
b = 2
for i in range(3, n + 1):
if i & 1:
a = (a + b) % MOD
else:
b = (a + b) % MOD
return a if n & 1 else b
print(solution(n))
채점 결과
