[백준] 2193 이친수 - Java

 

 

 

간단한 dp문제다.

 

이차원 dp배열을 설정해서 풀이한다. 

[N+1][2] : N은 자릿수 / 2는 0으로 끝나는 수와 1로 끝나는 수.

 

다음 자릿수의 이친수를 구할 때는 이전 자릿수의 이친수가 0으로 끝난 경우 + 1로 끝난 경우 + 0으로 끝난 경우를 계산해주면 된다..

 

 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        
        long[][] dp = new long[N+1][2];

        if(N == 1){
            System.out.println(1);
            return;
        }

        if(N == 2){
            System.out.println(1);
            return;
        }

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

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

        for(int i=3; i<N+1; i++){
            dp[i][0] = dp[i-1][0] + dp[i-1][1];
            dp[i][1] = dp[i-1][0];
        }

        System.out.println(dp[N][0] + dp[N][1]);
        
        

    }
}

 

 

 

경계에 걸친 테스트케이스 처리를 기억하자.