[백준] 2193번 이친수 - Java, 자바

난이도

실버 3

문제

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

풀이

1. 테이블 정의하기
   dp[i][j] j로 끝나는 i자리 이친수의 개수

2. 점화식 세우기
   j=0 일 때, dp[3][0] = dp[2][0] + dp[2][1]
   j=1 일 때, dp[3][1] = dp[2][0]

3. 초기값 정하기
   dp[1][0] = 0
   dp[1][1] = 1

코드

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

// 2193번 이친수
public class boj_9_2193 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        long D[][] = new long[91][2];

        D[1][0] = 0;
        D[1][1] = 1;

        for (int i = 2; i <= n; i++) {
            D[i][0] = D[i - 1][0] + D[i - 1][1];
            D[i][1] = D[i - 1][0];
        }

        System.out.println(D[n][0] + D[n][1]);
    }
}