[백준 2193] 이친수 (DP 동적프로그래밍)

https://www.acmicpc.net/problem/2193

2193번: 이친수

 

이번 문제도 먼저 떠오른 방법은 DFS (깊이 우선 탐색) 이었다.

#include <iostream>
 
using namespace std;
 
int N;
int arr[91];
long long count = 0;
 
void one(int i);
void zero(int i);
 
 
int main() {
  cin >> N;
  one(N);
  cout << count;
}
 
 
void zero(int i){
  arr[i] = 0;
  if(i==1) count++;
  else{
    zero(i-1);
    one(i-1);
  }
}
 
void one(int i){
  arr[i] = 1;
  if(i==1) count++;
  else{
    zero(i-1);
  }
}
 

 

 

하지만 시간초과로 실패했다.

DP로 문제를 푸는 방법을 구글링 하면서 힌트를 얻고 다시 코드를 짰다.

이번에는 틀렸습니다가 떴는데, 30분 정도 고민하고 알아낸 문제는 int 였다.

long long 으로 바꿔주니까 해결.

#include <iostream>
using namespace std;
 
int main() {
  long long N;
  long long arr[91][2];
  cin >> N;
 
  arr[N][0] = 0;
  arr[N][1] = 1;
 
  for(int i = N - 1; i > 0; i--){
    arr[i][0] = arr[i+1][0] + arr[i+1][1];
    arr[i][1] = arr[i+1][0];
  }
 
  cout << arr[1][0] + arr[1][1];
}

 

 

이런 식으로 글을 쓰면 다른 사람은 고사하고 나한테도 별로 도움이 안될 것 같아서 고민이다.

하지만 깔끔하게 쓰는 정성을 들이기는 너무 귀찮고 시간이 아깝다.