[파이썬] 백준 2193 : 이친수 (실버3)
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
문제
풀이
방향성 생각
- 2가지 상태가 나누어진 DP
- 현재 1인경우 다음은 0
- 현재 0인경우 다음은 0 또는 1
전체코드
n = int(input())
dp = [[0]*n for _ in range(2)]
dp[1][0] = 1
for i in range(n-1):
dp[0][i+1] += (dp[0][i] + dp[1][i])
dp[1][i+1] += dp[0][i]
print(dp[0][-1]+dp[1][-1])
코멘트
'Algorithm > Dynamic Programming' 카테고리의 다른 글
| [파이썬] 백준 18244 : 변형 계단 수 (골드3) (0) | 2023.11.23 |
|---|---|
| [파이썬] 백준 1636 : 한번 열면 멈출 수 없어 (골드4) (0) | 2023.11.05 |
| [파이썬] 백준 14550 : 마리오 파티 (골드5) (0) | 2023.10.22 |
| [파이썬] 백준 1577 : 도로의 개수 (골드5) (0) | 2023.09.29 |
| [파이썬] 백준 2758: 로또 (골드4) (0) | 2023.09.25 |
| [파이썬] 백준 2602 : 돌다리 건너기 (골드4) (0) | 2023.09.13 |
| [파이썬] 백준 20303: 할로윈의 양아치 (골드3) (0) | 2023.09.07 |
댓글