문제링크
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
|
import sys
input = sys.stdin.readline
n = int(input())
d = [[0]*2 for _ in range(91)]
d[1] = [0,1]
for i in range(2,n+1):
d[i][0] = d[i-1][0]+d[i-1][1]
d[i][1] = d[i-1][0]
print(sum(d[n]))
|
cs |
POINT
- DP로 접근
- 풀이 방법:
1이 두번 연속 나타나지 않기 위해서 마지막 수를 저장하는 전략을 채택한다.
'd[i][j] = 총 길이가 i이고, 마지막 수가 j인 이친수 갯수' 라고 정의한다.
1을 추가하려면 1이 연속되지 않기 위해서, 직전 수가 0인 경우에만 1을 추가할 수 있다. ==> d[i][1] = d[i-1][0]
0을 추가하려면 직전 수가 0이든 1이든 상관없이 가능하다. ==> d[i][0] = d[i-1][0]+d[i-1][1]
'Algorithm > Baekjoon' 카테고리의 다른 글
| [백준]1912 연속합 파이썬 python (0) | 2022.02.14 |
|---|---|
| [백준]11053 가장 긴 증가하는 부분 수열 14002 가장 긴 증가하는 부분 수열 4 파이썬 얕은 복사 python (0) | 2022.02.09 |
| [백준]10844 쉬운 계단 파이썬 python (0) | 2022.02.08 |
| [백준]15990 1, 2, 3더하기 5 파이썬 python (0) | 2022.02.07 |
| [백준]11052 카드구매하기 16194 카드구매하기2 파이썬 python (0) | 2022.02.06 |