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자리 이친수의 개수를 출력한다.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	91755	39024	29652	41.053%

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

풀이

방법 1 (역순)

문제를 살펴보면 아래와 같이 두가지의 규칙을 볼수있다.

1. 이친수는 0으로 시작하지 않음.
2. 이친수는 1이 두번 연속으로 나타나지않음.

살펴보면 아래와 같이 설명할수있다.

1) 4자리수 중 2개는 3자리수의 모든 개수와 같다.
2) 4자리수 중 1개는 2자리수의 모든 개수와 같다.

이는 n=5 일때도 적용된다.

1) 5자리수 중 3개는 4자리수의 모든 개수와 같다.
2) 5자리수 중 2개는 3자리수의 모든 개수와 같다.

이를 통해 점화식을 구하면

dp[n] = dp[n-1] + dp[n-2] 

다음으로 이문제를 보면 n의 범위가 1~90까지 이다. n=90일 경우를 보면 46항이 될때, 2971215073이 되어, int의 범위를 초과하게 된다. 즉, 특정수로 나눈 나머지값(모듈러)를 사용해서 출력하거나, int 이상의 자료형을 이용해야한다. (이해가 안간다면 문제의 점화식을 보면된다. 이 점화식은 피보나치수열과 같은것을 볼수있는데, 피보나치 수열을 대입해서 계산해보면 답이 나온다... 기하급수적으로 증가된다.) 어쨋든 이러한 이유 때문에 long자료형을 사용해야한다!

코드

import java.io.BufferedReader; 
import java.io.InputStreamReader; 

public class Main { 
    static int n; 
    static long dp[] = new long[91]; 
    public static void main(String[] args) throws Exception {
         BufferedReader br = new BufferedReader(new 
         InputStreamReader(System.in)); 
         n = Integer.parseInt(br.readLine()); 
         dp[0] = 0;
         dp[1] = 1; 
          for (int i = 2; i <= n; i++) { 
              dp[i] = dp[i-1] + dp[i-2];  //점화식 대입.
              }
            System.out.println(dp[n]); 
        } 
    }

다음 방법도 살펴보자.

방법2(이차원배열)

살펴보면, 3자리수에서 4자리수가 되는 부분이다. 이때 추가되는 부분은 빨간색으로 표시한것이다.

규칙을 살펴보면, 이친수에서 1이 두번 연속으로 나타나지 않으므로 11이 나타나는것은 불가능하다. 즉 마지막의 끝나는 수를 기준으로 살펴보면 될것이다. 3자리수에서 마지막에 끝나는수가 0일 경우에는 0,1 이 들어올수있고, 1일경우에는 0만 가능하다.

A : 0으로 시작되는 경우 : 00 01 가능

dp[4][0] = dp[3][0] + dp[3][1]

B: 1로 시작되는 경우: 10 가능

dp[4][1] = dp[3][0]

이렇게 나타낼수 있겠다. 이를 통해 점화식을 뽑아보면?

dp[n][0] = dp[n-1][0] + dp[n-1][1]
dp[n][1] = dp[n-1][0]

이렇게 나눠서 구해지게 된다. 그리고 두가지 경우를 합쳐준다면 원하는 답을 구할수있다.

코드

package 기초1.Day16.정해영;  

import java.util.Scanner;  

public class 이친수 {  

public static void main(String[] args) {  
Scanner sc = new Scanner(System.in);  

int n = sc.nextInt();  

long[][] dp = new long[n+1][2]; //int 형 선언시에 범위가 초과된다.  

/*  
이렇게 이해하자. n=2 일때, 2자리수 00 01 10 11 이렇게 나올것이다.  
여기서 dp[자리수][마지막뒷자리] = 이친수의 개수 로 선언하자.  
즉, dp[2][0] 이라면 {0}0 {0}1 이렇게 될것이고, 이친수의 갯수는 0이다. 왜나하면 제일앞에는 0일수가 없기때문.  
dp[2][1] 이라면 {1}0 {1}1 이렇게 될것이다. 이친수의 개수는 1이다.  
*/  

dp[1][1] = 1;  
dp[1][0] = 0;  

for(int i=2; i<=n; i++){  
dp[i][0] = dp[i-1][0] + dp[i-1][1]; //[4][0] -> {100}0, {100}1  
dp[i][1] = dp[i-1][0]; // [4][1] -> {101}0 이런식으로...!  
}  

System.out.println(dp[n][0] + dp[n][1]);  
sc.close();  
}  
}