[백준/DP] 2193번 이친수 (JAVA)

문제

---

풀이

점화식은 바로 떠올렸는데, int 범위를 벗어나서 계속 오답으로 뜨는 바람에 잠깐 삽질을 했다. n이 최대 90까지이므로, dp 배열을 long으로 선언해줘야 값을 온전하게 담을 수 있다.

1. n >= 3인 경우, 조건에 의해 맨 앞 두 자리는 10으로 고정이 된다.
2. 세 번째 자리에 1을 넣는 경우, 그 다음 네 번째 자리는 자동으로 0이 되므로, 나머지 자리를 채우는 경우의 수는 dp[n-2]와 같다.
3. 세 번째 자리에 0을 넣는 경우, 나머지 자리를 채우는 경우의 수는 dp[n-1]과 같다.

따라서 점화식은 피보나치 수열과 동일한 dp[n] = dp[n-1] + dp[n-2]이다.
이를 코드로 표현하면 아래와 같다.

코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 90;

    private static int n;
    private static long[] dp = new long[MAXIMUM + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        dp();
        bw.append(String.valueOf(dp[n]));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
    }
}