차근차근
[백준 1904] 01타일 본문
0. 제목
- 백준 1904 01타일
- BOJ 1904 01타일
- 파이썬 1904 01타일
- Python 1904 01타일
1. 문제
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] 평범한 배낭 (278) | 2020.09.11 |
[백준 1325] 효율적인 해킹 (416) | 2020.09.09 |
[백준 1012] 유기농 배추 (0) | 2020.09.08 |
[백준 2606] 바이러스 (0) | 2020.09.08 |
Comments