[백준] 1904번_01타일(Java)

문제 풀이

백준의 1904번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

\(P[a] = P[a-1] + P[a-2]\)

여기서 주의해야 할 점은 N이 1,000,000까지 가게 되면 int나 long의 범위를 넘어설 수 있습니다.

그러므로 값 자체를 저장하는 것이 아닌 15746으로 나눈 값의 나머지를 저장하여 오버플로우를 방지해야 합니다.

(3) 시간 복잡도 확인

시간 제한은 0.75초입니다. N의 최대 값은 1,000,000이기 떄문에 미리 1,000,000까지의 값을 모두 계산한다면 O(N)이므로 괜찮습니다!

(4) 구현

import java.io.*;

public class Main {
	static final int N = 1_000_001;
    static int[] arr = new int[N];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());
        
		solution();

        System.out.println(arr[number]%15746);
        
        br.close();
    }
    
    static void solution() {
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 2;

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