[Java] 2193번: 이친수 Silver 3

문제 링크

3, 4, 5 번을 풀어봤다면, 5번도 쉽게 풀 수 있을 것이다.

규칙은 이렇다.
1. N-1의 케이스에서 0을 붙이는 경우
2. N-2의 케이스에서 01을 붙이는 경우

점화식을 구해서 바로 코드를 작성해보자!

X[N] = X[N-1] + X[N-2]

정답

다만 이번에는 다른 문제들처럼 중간에 값을 나눠서 오버플로우를 방지하는 부분이없다.
그러니 long 타입으로 선언해서 풀자!

import java.io.*;
import java.util.*;

public class Main {
    private static int N;
    private static long[] dp;

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

        // N 입력 받기
        N = Integer.parseInt(br.readLine());

        // dp
        if (N == 1) {
            System.out.println(1);
        } else if (N == 2) {
            System.out.println(1);
        } else {
            dp = new long[N + 1];
            dp[1] = 1;
            dp[2] = 1;
            for (int i = 3; i <= N; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }

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

물론 메모리를 더 최적화하고 싶다면 배열에 저장없이 long 변수에 바로 저장해서 출력에 사용해도 된다!
(애초에 연산이 별로 없어서 거의 차이는 없다..)

long a = 1;
long b = 1;
long copy;
for (int i = 3; i <= N; i++) {
	copy = b;
	b = a + b;
	a = copy;
}