[백준][c++] 2193번: 이친수

2193번: 이친수 (acmicpc.net)

문제 해석

• dp를 이용한 경우의 수 찾기

알고리즘 분류

• dp

풀이

• arr[i][1] = arr[i - 1][0];
  arr[i][0] = arr[i - 1][0] + arr[i - 1][1];
• 점화식을 이용하여 배열을 채운다

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n;
vector<vector<long>> arr;

int main() { 
  cin >> n;
  arr.resize(n + 1, vector<long>(2));
  arr[1][0] = 0;
  arr[1][1] = 1;

  for (int i = 2; i <= n; i++) {
    arr[i][1] = arr[i - 1][0];
    arr[i][0] = arr[i - 1][0] + arr[i - 1][1];
  }
  cout << arr[n][1] + arr[n][0]; 
}