https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 규칙성을 파악하면 쉽게 해결할 수 있는 문제였습니다. n에 따른 이친수는 각각 다음과 같습니다.
n = 1 일때, 1 즉 1개
n = 2 일때, 10 즉 1개
n = 3 일때, 100, 101 즉 2개
n = 4 일때, 1000, 1001, 1010 즉 3개
n = 5 일때, 10000, 10001, 10010, 10100, 10101 즉 5개
따라서 이는 피보나치 수열의 형태임을 알 수 있다. 이를 소스코드로 옮기면 다음과 같다.
소스코드 - python
|
1
2
3
4
5
6
7
8
9
|
n = int(input())
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n-1])
|
cs |
소스코드 - c++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <bits/stdc++.h>
#define MAX 91
using namespace std;
int main(void) {
int n;
scanf("%d", &n);
long long dp[MAX] = {0, };
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i < n+1; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
printf("%lld", dp[n-1]);
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 11052번: 카드 구매하기(Python) (0) | 2022.02.02 |
|---|---|
| 백준 알고리즘 9461번: 파도반 수열(Python) (0) | 2022.01.31 |
| 백준 알고리즘 11057번: 오르막 수(Python) (0) | 2022.01.29 |
| 백준 알고리즘 9251번: LCS(Python) (0) | 2022.01.29 |
| 백준 알고리즘 1904번: 01타일(Python) (0) | 2022.01.28 |