[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 2193

n자리의 이진수 중 1이 연속하지 않는 수인 이친수의 갯수를 구하기

 

- d[n+1][3]짜리 배열을 생성, n의 최댓값 90일 때 int의 범위를 넘어가므로 long타입으로 지정한다.

- d[i][j]: i자리의 이진수 중 j로 끝나는 이친수의 갯수

 

- i자리이고 1로 끝나는 이친수의 갯수는, i-1자리이고 0으로 끝나는 이친수의 갯수와 같다.

- i자리이고 0로 끝나는 이친수의 갯수는, i-1자리이고 0, 1로 끝나는 이친수의 갯수와 같다.

- 즉, d[i][1]=d[i-1][0], d[i][1]=d[i-1][0]+d[i-1][1] 이다.

 

- 한자리 수인 이친수는 1뿐이므로, 1로 예외처리하여 저장한다.

import java.util.Scanner;

public class BOJ2193 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        long [][]d=new long[n+1][3];

        for(int i=1;i<=n;i++){
            for(int j=0;j<=1;j++) {
                if (i == 1) {
                    d[1][1] = 1;
                }
                else if(j==0){
                    d[i][j] = d[i - 1][1]+d[i-1][0];
                }
                else {
                    d[i][j] = d[i - 1][0];
                }
            }
        }
        System.out.println(d[n][0]+d[n][1]);
    }
}