DHistory
[Baekjoon] DP - 1904 01타일 본문
문제
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))
채점 결과
'Computer Science > Algorithm' 카테고리의 다른 글
| [Baekjoon] DP - 1912 연속합 (0) | 2023.09.25 |
|---|---|
| [Baekjoon] DP - 11053 가장 긴 증가하는 부분 수열 (오답노트) (0) | 2023.09.25 |
| [Baekjoon] DP - 2193 이친수 (1) | 2023.09.20 |
| [Baekjoon] DP - 9461 파도반 수열 (0) | 2023.09.19 |
| [Baekjoon] DP - 2579 계단 오르기 (0) | 2023.09.19 |