반응형
문제
https://www.acmicpc.net/problem/2193
풀이
N번째 자리에 올 수 있는 수는 0 또는 1이다.
○ ○ ○ .... ☆ ● 에서
만약 ●에 0이 온다면 ☆에는 0 또는 1이 올 수 있다. 따라서 n-1에 오는 수에 따라 개수가 결정이 된다.
반대로 ●에 1이 온다면 ☆에는 0만 올 수 있다. 따라서 n-2에 오는 수에 따라 개수가 결정이 된다.
D[N] = N자리 이친수의 개수라고 하면 다음과 같은 점화식을 구할 수 있다.
D[N] = D[N-1] + D[N-2]
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <iostream>
using namespace std;
int N;
long long dp[91];
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= N; i++) dp[i] = dp[i - 1] + dp[i - 2];
cout << dp[N];
return 0;
}
|
cs |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <iostream>
using namespace std;
int N;
long long dp[91][2];
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
dp[1][0] = 0; dp[1][1] = 1;
dp[2][0] = 1; dp[2][1] = 0;
for (int i = 3; i <= N; i++)
{
dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
dp[i][1] = dp[i - 1][0];
}
cout << dp[N][0] + dp[N][1];
return 0;
}
|
cs |
dp[N][L] = N번째 자리에 오는 마지막 수 L로 하는 풀이다.
L=0 이면 N-1 번째 자리에는 0이랑 1이 올 수 있지만,
L=1 이면 N-1 번째 자리에는 0만 올 수있다.
반응형
'BOJ' 카테고리의 다른 글
백준 2503 - 숫자 야구 (0) | 2019.06.01 |
---|---|
백준 2644 - 촌수계산 (0) | 2019.05.30 |
백준 1473 - 음식물 피하기 (0) | 2019.05.23 |
백준 1012 - 유기농 배추 (0) | 2019.05.18 |
백준 1629 - 곱셈 (0) | 2019.05.16 |