[C/C++] 2193: 이친수

2193: 이친수 문제

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

2193번: 이친수

이 문제 역시 2차원 배열 dp[][]을 이용하여 풀었다.

dp[i][0]에는 길이가 i인 이친수 중 0으로 끝나는 수의 개수를

dp[i][1]에는 길이가 i인 이친수 중 1로 끝나는 수의 개수를

dp[i][2]에는 길이가 i인 이친수의 개수를 저장하였다.

 

이렇게 나눈 이유는 마지막이 0으로 끝나면 그 다음에는 0과 1 모두 올 수 있지만

1로 끝나게 된다면 그 다음에 0밖에 못온다. 

그렇기 때문에 이를 점화식으로 표현하게 된다면 

 dp[i][0]=dp[i-1][0]+dp[i-1][1]; 
 dp[i][1]=dp[i-1][0]; 
 dp[i][2]=dp[i][0]+dp[i][1];

이 된다.

 

그리고 한가지 주의해야할 점은 N이 50정도만 되어도 그 수가 매우 커져 int형 변수로 표현할 수가 없다.

그렇기 때문에 dp배열을 long long int로 잡아야만 변수로 표현할 수 있다!

 

이를 이용하여 코드를 작성하면 아래와 같이 된다!

#include <stdio.h>

long long int dp[101][3]; //0으로 끝남, 1로 끝남,이친수의 개수

int main(void)
  {
    int n;
    scanf("%d",&n);
    dp[1][0]=0;
    dp[1][1]=1;
    dp[1][2]=1;
    for(int i=2;i<=n;i++)
      {
        dp[i][0]=dp[i-1][0]+dp[i-1][1]; //1-0 과 0-0(0은 연속으로 나와도 상관X)
        dp[i][1]=dp[i-1][0]; // 0-1만 가능(1이 연속으로 나오면 안됨)
        dp[i][2]=dp[i][0]+dp[i][1];
      }
    printf("%lld",dp[n][2]);
  }