[백준 / JAVA] 2193번 이친수

문제

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

접근

이친수의 조건: 이진수, 1로 시작함, 1이 연속되지 않음.
ex) 1, 10, 100, 101...

가장 먼저 들었던 생각은 가장 앞자리를 1로 놓고 그 뒷자리를 0과 1 중 가능한 숫자로 채워 나가는 완전 탐색 방식을 생각했다.
하지만 DP를 연습하기 위해 패스.

트리를 그려 n자리 이친수의 규칙성을 파악하고자 했다.
위의 트리를 보면 n일 때 총개수가 n - 1일 때의 0 개수와 연관이 있다는 걸 알 수 있다.

예를 들어 n이 4일 때 이친수는 1010, 1001, 1000.
0 뒤에 나올 수 있는 수는 0과 1.
1 뒤에 나올 수 있는 수는 0.
따라서 n이 5일 때 이친수의 개수는 3 + 2 = 5.

그렇다면 n - 1일 때의 0 개수는 어떻게 구할까.
그건 n - 2의 총개수를 보면 알 수 있다.

앞서 언급했듯이 0은 0과 1 뒤에 무조건 나오기 때문에
n - 1일 때 0의 개수 == n - 2의 총개수.

따라서 n자리 이친수 개수 = (n - 1)자리 이친수 개수 + (n - 2)자리 이친수 개수
DP 배열에 memoization 하여 해결 가능.

풀이

import java.util.Scanner;

public class boj_2193 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        long[] dp = new long[n + 1];

        if (n >= 1) dp[1] = 1;
        if (n >= 2) dp[2] = 1;

        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];

        System.out.println(dp[n]);
    }
}

정리

DP의 개념을 알고 중첩 부분 문제를 파악하면 쉬운 문제.
주의할 점은 최초에 dp 배열을 int형으로 선언했다가 오답 처리됨. n에 90을 넣었더니 overflow가 발생하는 것을 확인했다.
자료형 선택을 항상 유의할 것!