Notice
Recent Posts
Recent Comments
Link
차근차근
[백준 1904] 01타일 본문
0. 제목
- 백준 1904 01타일
- BOJ 1904 01타일
- 파이썬 1904 01타일
- Python 1904 01타일
1. 문제
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이��
www.acmicpc.net
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. 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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' 카테고리의 다른 글
[백준 11053] 가장 긴 증가하는 부분 수열 (0) | 2020.09.12 |
---|---|
[백준 12865] 평범한 배낭 (0) | 2020.09.11 |
[백준 1325] 효율적인 해킹 (0) | 2020.09.09 |
[백준 1012] 유기농 배추 (0) | 2020.09.08 |
[백준 2606] 바이러스 (0) | 2020.09.08 |
0 Comments