[백준 2193 c++ VO] 이친수

##새로운 풀이

: 정석 2차원 dP

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// [백준 2193 c++ VO] 이친수 
// 문제: n 자리 이친수의 개수 구하기 
// 접근1: dp결과값으로 규칙 찾기 -> dp[n] = dp[n-1]+dp[n-2] => 이것도 정답
// 접근2: 2차원 dp : 0으로 끝나는 경우, 1로 끝난는 경우 => 정석 dp
// 풀이: 
// 점화식 dp 작성
// dp 점화식: 
// 0으로 끝나는 경우 dp[i][0] = dp[i-1][0] + dp[i-1][1]
// 1로 끝나는 경우 dp[i][1] = dp[i-1][0] 
// 정답 출력
// 주의
// : 범위 long long 으로 해야 함
#define MAX 91
int n;
vector<vector<long long>> dp(MAX,vector<long long>(2));
 
int main()
{    
    ios::sync_with_stdio(false); // 계산시간 단축 // 문제마다 오류 유무 다름
    cin.tie(NULL); cout.tie(NULL);// 입출력 시간 단축
 
    cin >> n;
    // dp 점화식: 
    // 0으로 끝나는 경우 dp[i][0] = dp[i-1][0] + dp[i-1][1]
    // 1로 끝나는 경우 dp[i][1] = dp[i-1][0] 
    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]; // 0으로 끝나는 경우
        dp[i][1] = dp[i - 1][0]; // 1로 끝나는 경우
    }
    // 정답 출력
    long long answer = 0;
    for (int i = 0; i <=1; i++) {
        answer += dp[n][i];
    }
    cout << answer << '\n';
    
    return 0;
}

 

##예전 풀이

: dp결과값 자체에서 규칙찾기

 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<deque>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);
 
// [백준 2193 c++ V] 이친수 
// 문제: n 자리 이친수의 개수 구하기 
// 접근1: 이친수의 맨 끝 자리가 0이면 다음 수 2개, 1이면 다음수 1개
// 점근2: 전화식으로 표현을 잘 못해서 각 dp 값의 규칙 찾으려 함
// 풀이: dp[0] ,dp[1]값은 고정,
// dp 점화식 dp[n] = dp[n-1]+dp[n-2] 으로 dp 배열 구함
// 주의: dp값이 인덱스가 90이어도 숫자가 커서 long long 자료형 써야 됨
 
using namespace std; // cin,cout 편하게 사용 라이브러리 
#define MAX 91
 
int n;
long long dp[MAX];
int ar[MAX];
 
int main()
{
    // IO 속도 향상
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);// 입출력 시간 단축
    cin >> n;
    dp[0] = 1;
    if (n > 1) dp[1] = 1;
    for (int i = 2; i < n; i++) {
        // dp 점화식 dp[n] = dp[n-1]+dp[n-2]
        dp[i] = dp[i - 1] + dp[i - 2];
    }
 
    cout << dp[n - 1];
 
    return 0;
}