[백준]2193번: 이친수

풀이

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

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[] arr = new long[N + 1];

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

        System.out.println(arr[N]);
    }
}

1. 해당 문제는 dp로 접근해야 한다.

   • 0으로 시작하지 않는다.
   • 1이 두 번 연속으로 나타나지 않는다.

   • N=1 : 1 => 1가지
   • N=2 : 10 => 1가지
   • N=3 : 100, 101 => 2가지
   • N=4 : 1000, 1001, 1010 => 3가지
   • N=5 : 10000, 10001, 10010, 10100, 10101 => 5가지

   => arr[i] = arr[i-1] + arr[i-2]

2. 해당 배열은 정수형 범위를 넘어가기 때문에 long형으로 지정한다.

3. arr[2]를 arr[0], arr[1]과 같이 지정하지 못한다. => 런타임 에러