[백준 2193] 이친수

www.acmicpc.net/problem/2193

2193번: 이친수

 

dp 사용

문제 규칙에 따라 11은 올 수 없고 0으로 시작하는 숫자도 올 수 없다.

n = 1일 경우 1

n = 2일 경우 10

n = 3일 경우 101 100

n = 4일 경우 1010 1000 1001

 

이전 단계에서 0과 1의 개수에 따라 다음 단계에서 만들 수 있는 숫자의 수가 정해지는 걸 확인할 수 있다.

그래서 zero를 저장하는 dp와 one을 저장하는 dp를 따로 만들어줬다.

one[i] 는 이전 zero에서 밖에 만들지 못하므로 one[i] = zero[i-1]이고 zero[i]는 이전 1과 0에서 모두 만들 수 있기 때문에 zero[i] = zero[i-1] + one[i-1]이다.

이 때 int로 배열을 설정하면 90까지 갔을 때 오버플로우가 난다. 따라서 long long으로 선언해야 한다.

 

++ 다른 접근법

결국 2이상의 숫자에서 10은 앞에 고정이다.

그러면 나머지 n-2자리에 뭐가 오느냐는 건데 dp[n-1]은 앞에 1을 빼고 나면 0으로 시작하는 이친수, dp[n-2]는 1로 시작하는 이친수이다. 

그래서 dp[n] = dp[n-1] + dp[n-2]가 된다.

#include <stdio.h>

using namespace std;

long long zero[91];
long long one[91];
int main(void)
{
  zero[0] = 0, one[0] = 0, zero[1] = 0, one[1] = 1;

  int n;
  scanf("%d", &n);

  for (int i = 2; i <= n; i++)
  {
    zero[i] = one[i - 1] + zero[i - 1];
    one[i] = zero[i - 1];
  }
  printf("%lld\n", one[n] + zero[n]);
  return 0;
}