[JAVA] 백준 2193번 : 이친수

[문제]

[입력]

첫째 줄에 N이 주어진다.

[출력]

첫째 줄에 N자리 이친수의 개수를 출력한다.

[예제 입력]

[풀이 과정]

정말 오랜만에 풀어보는 DP... 실버임에도 불구하고 머리가 돌아가지 않았다.. 흑흑

 

 

문제와 조건은 간단하다.

 

이진수가 있다.  

 

조건 1 ) 첫째 자리는 0으로 시작하지 않는다.

조건 2 ) 1이 두 번 연속해서 나오지 않는다.

 

조건에 해당하는 이진수의 개수를 찾는 문제이다.

 

최대 N=90이기 때문에 완전 탐색으로 풀 수 없는 문제이다. (경우의 수가 엄~~~청 큼)

 

이 문제에서 신경써야 할 부분은 조건 2이다. 1이 연속해서 두 번 나오지 않는다는 것. 이를 잘 이용하면 간단하게 풀 수 있다.

 

맨 오른쪽 끝 자리에 0을 넣을지 1을 넣을지에 대해서 생각하면 된다.

 

예를 들자면

 

N = 1일경우 ,  "1" 딱 한 가지 경우가 존재한다. 

N = 2일 경우 , "10" 딱 한 가지 경우가 존재한다.  그리고 N >=2 일 때는 반드시 앞에 "10"으로 시작해야 한다.

N= 3일 경우, "10_"의 경우 일 거다.  _에는 0 또는 1이 올 수 있다. 따라서 경우의 수는 2이다.

N= 4일 경우, 맨 뒷자리에 집중해보자.

 

이해가 될지 모르겠지만 .. 차근히 해보자

따라서 N=이 4일 때는 N=3인 경우와 N=2인 경우의 수를 합한 값이 된다.

 

이를 통해 다음과 같은 점화식을 세울 수 있다.

d[i] = d[i-1] (0또는 1이 오는 경우니까 i-1 경우와 같음) 
     + d[i-2] (i에 1이 왔고 i-1에는 반드시 0이 와야함 이 뒤에 i-2부터는 또 0또는 1이 오니까 i-2경우와 같음)

[코드]

package Silver;

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

public class Main2193 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        long [] answer = new long[N+1]; // 정수형 범위를 초과하는 것에 주의한다.

        answer[0] = 0;
        answer[1] = 1;



        for( int i =2; i<=N; i++){
            answer[i] = answer[i-1]+answer[i-2];
        }

        System.out.println(answer[N]);

    }
}

 

[결과]