문제 링크
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
풀이
- dp 문제, 점화식 문제
- 문제를 풀다보니 dp 문제는 점화식 또는 메모제이션 유형으로 나눌 수 있을 것 같다.
- 점화식 result[i] = result [i-2] + result[i-1]
n = int(input())
if n == 1 or n == 2:
print(1)
else:
result = [0] * (n+1)
result[0] = 1
result[1] = 1
for i in range(2, n):
result[i] = result[i-1] + result[i-2]
print(result[n-1])'개발 > algorithm' 카테고리의 다른 글
| [백준 12865번] 평범한 배낭 -python (0) | 2022.01.27 |
|---|---|
| [백준 2292번] 동전1 -python (0) | 2022.01.27 |
| [백준 14395번] 4연산 -python (0) | 2022.01.27 |
| [백준 2206번] 벽 부수고 이동하기 - python (0) | 2022.01.27 |
| [백준 1303번] 전쟁 - 전투 -python (0) | 2022.01.26 |