Algorithm_BOJ(백준)/동적프로그래밍(DP)
[백준 2193 c++ VOO] 이친수
xhaktmchl
2021. 7. 24. 16:22
728x90
반응형
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
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
using namespace std;
// [백준 2193 c++ VOO] 이친수
// 문제: n 자리 이친수의 개수 구하기
// 접근1: dp결과값으로 규칙 찾기 -> 못찾음
// 접근2: 2차원 dp : 0으로 끝나는 경우, 1로 끝난는 경우
// 풀이:
// 점화식 dp 작성
// dp 점화식:
// 0으로 끝나는 경우 dp[i][0] = dp[i-1][0] + dp[i-1][1]
// 1로 끝나는 경우 dp[i][1] = dp[i-1][0]
// 정답 출력
#define MAX 91
int n;
long long dp[MAX][2];
int main()
{
ios::sync_with_stdio(false); // 계산시간 단축 // 문제마다 오류 유무 다름
cin.tie(nullptr); cout.tie(nullptr);// 입출력 시간 단축 // 이것을 쓰면 scanf,printf섞어 쓰면 안됨
cin >> n;
// 바텀업 dp 구현
// dp 점화식:
// 0으로 끝나는 이친수( :dp[i][0] = dp[i - 1][1] + dp[i - 1][0];
// 1로 끝나는 이친수 : dp[i][1] = dp[i - 1][0];
dp[1][0] = 0; dp[1][1] = 1;
for (int i = 2; i <= n; i++) {
dp[i][0] = dp[i - 1][1] + dp[i - 1][0];// 0으로 끝나는 경우
dp[i][1] = dp[i - 1][0]; // 1로 끝나는 경우
}
// 이친수 갯수 출력
cout << dp[n][0] + dp[n][1] << '\n';
return 0;
}
|
cs |
반응형