[BOJ / C++] 이친수 (다이나믹 프로그래밍)

문제링크: https://www.acmicpc.net/problem/2193

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;

    vector<vector<ll>> d(92, vector<ll>(2, 0));
    d[1][0] = 0;
    d[1][1] = 1;
    for (int i = 2; i <= 90; i++) {
        d[i][0] = d[i-1][0] + d[i-1][1];
        d[i][1] = d[i-1][0];
    }

    cout << d[n][0] + d[n][1];
}

 

 

2. 시간복잡도

90번만 연산하면 끝나므로 시간제한 2초 안에 해결 가능하다.

 

 

3. 분석

1. dp 테이블

(1) 끝에가 0인 경우: 앞에 1, 0 모두 올 수 있음.

(2) 끝에가 1인 경우: 앞에 0만 올 수 있음, 1이 2개 연속 올 수 없기 때문에

 

2. 점화식

d[i][0] = d[i-1][0] + d[i-1][1];

d[i][1] = d[i-1][0];

 

vector의 자료형이 int가 되면 int overflow가 발생한다. dp에서 피보나치 형식의 덧셈이 될 경우 40만 넘어가도 int overflow가 될 확률이 높다. long long 자료형을 쓰도록 하자!