[백준 알고리즘] 2193번 이친수

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이를 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 

예를 들면 1, 10,100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1≤N≤90)이 주어졌을 때 N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력과 출력

첫째줄에 N이 주어지면 N자리 이친수의 개수를 출력

풀이

다이나믹 프로그래밍 문제만 찾아풀고있어서 이 문제가 DP라는 것만 알고 사실 왜 다이나믹으로 풀어야하는지 감이 안온다......

앞에 풀었던 방법들로 1자리수부터 생각하면 f(n)은 n자리 이친수의 개수를 구해야한다

근데 n 하나의 변수만으로 이친수를 구할 수 없는거같다

f(n,0) f(n,1) 두가지의 경우로 나눠서

f(n,0) -> n자리의 이진수 중에서 연속되는 11을 가지지 않고 0으로 시작하는 이진수의 수

f(n,1) -> n자리의 이진수 중에서 연속되는 11을 가지지 않고 1로 시작하는 이진수의 수

f(1, 0) = 1 

f(1, 1) = 1

f(2, 0) = f(1, 0)+f(1, 1)

f(2, 1) = f(1, 0) ->앞에 1로 시작하니까 f(1,0)만 가능

f(3, 0) = f(2, 0)+f(2, 1)

f(3, 1) = f(2, 0)

f(n, 0) = f(n-1, 0) + f(n-1, 1)

f(n, 1) = f(n-1, 0)

헐 처음으로 완전히 혼자 점화식 세워봤다..

코드

  int i

long long dp[100][2];

scanf("%d", &n);

dp[1][0] = 1;

dp[1][1] = 1;

for(i=2; i<=n; i++)

{

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

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

}

printf("%lld", dp[n][1]); 

* 처음에 int로 배열만들었는데 int범위를 넘어가는 경우가 있어서 틀렸습니다가 나왔다.... 타입때문일줄이야 long long 으로 타입만 바꿔주니 된다!