01타일 - 실버 3 (백준 , DP)
2023. 1. 18. 18:22ㆍ코딩 테스트 준비
728x90
반응형
fibo = [0] * 1000000
fibo[0] = 1
fibo[1] = 2
N = int(input())
if N == 1:
print(1)
elif N == 2:
print(2)
else:
for i in range(2, N):
fibo[i] = (fibo[i-2] + fibo[i-1])%15746
print(fibo[N-1])
피보나치인데 그걸 눈치를 못챘다...
잘 생각을 해보자 1에는 1이, 2에는 00이랑 11이 있다.
3이 되려면 100, 001, 111이다.
이는 1에 (1)00을 2에 (00,11)1을 더한 것이다.
4도 그렇다.
2에 (00,11)에 00, 3에 (100,001,111)에 1을 더한 값이다...
제발 잘 생각하고 너무 어렵게 보지말고 더해지는 것을 볼때 피보나치를 먼저 생각해서 차분히 보자.
728x90
반응형
'코딩 테스트 준비' 카테고리의 다른 글
| 수 이어 쓰기 1515번 - 실버 3 (백준, 문자열) (0) | 2023.01.19 |
|---|---|
| 나무 자르기 - 실버 2 (백준, 이분탐색) (0) | 2023.01.19 |
| NBA 농구 - 실버 3 (백준, 구현) (2) | 2023.01.18 |
| IF문 좀 대신 써줘 - 실버 3 (백준, 이분탐색) (0) | 2023.01.18 |
| 유기농 배추 - 실버 2 (백준, DFS/BFS) BFS만 (0) | 2023.01.18 |