https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
풀이 과정
D[n][k]를 k로 끝나는 n자리 이친수의 개수라고 하자
1이 두번 연속으로 나타나면 안된다는 문구를 보고 다음과 같은 2가지 방법을 생각할 수 있다.
1. D[n][0] = D[n-1][0] + D[n-1][1], D[n][1] = D[n-1][0] 꼴로 2차원 배열로 해결하기.
2. D[n] = D[n][0] + D[n][1] 이고 1번의 식에서 본 것 처럼 D[n][0] = D[n-1][0] + D[n-1][1] = D[n-1]이다. D[n][1]은 D[n-2]
01을 뒤에 붙여서 만들 수 있으므로 D[n] = D[n-1] + D[n-2]가 성립한다. 따라서 1차원 배열로도 해결할 수 있다.
2번 방법을 사용해 문제를 해결하였다.
소스 코드
d = [0 for _ in range(0, 91)]
d[1] = 1
d[2] = 1
for i in range(3, 91):
d[i] = d[i-1] + d[i-2]
N = int(input())
print(d[N])'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
| 백준 14002 - 가장 긴 증가하는 부분 수열 4 [파이썬] (0) | 2022.04.20 |
|---|---|
| 백준 11053 - 가장 긴 증가하는 부분 수열 [파이썬] (0) | 2022.04.20 |
| 백준 10844 - 쉬운 계단 수 [파이썬] (0) | 2022.04.20 |
| 백준 15990 - 1, 2, 3 더하기 5 [파이썬] (0) | 2022.04.20 |
| 백준 16194 - 카드 구매하기 2 [파이썬] (0) | 2022.04.11 |