[Baekjoon 2193] 이친수 - JAVA

[Silver III] 이친수 - 2193

문제 링크

성능 요약

메모리: 14320 KB, 시간: 124 ms

분류

다이나믹 프로그래밍

문제 설명

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

문제 풀이

2진수이기 때문에, n자리에 올 수 있는 수는 0과 1이 오는 경우만 생각하면 된다.

1) n자리에 오는 수가 0인 경우

n번째 자리에 0이 들어왔으므로 앞에는 0혹은 1 둘다 올 수 있다. (연속하는 11이 없기 때문에)

따라서 맨 끝에 0이오는 경우는 d[n-1]이다.

2) n자리에 오는 수가 1일때

n번째 자리에 1이 들어왔으므로 앞에는 0밖에 올수가 없다. (연속하는 11을 만들기 때문에)

따라서 n-1번째 자리가 0이므로 n-2번째 자리는 0 혹은 1이 올 수 있다.

따라서 맨 끝에 1이 오는 경우는 d[n-2]이다

점화식을 세우면 다음과 같다.

d[n] = d[n-1] + d[n-2]

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

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

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

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

늘 그렇듯 dp문제는 점화식을 찾느냐 마느냐로 풀수있는지 없는지가 결정되는것 같다.

점화식을 찾았으면 코드 풀이는 사실상 필요가 없다...