문제 분석
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| import java.io.*;
import java.util.*;
class Main {
// DP 테이블 선언
static int[] D;
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만큼의 01타일로 만들 수 있는 경우의 수는
// 피보나치 수열의 N번째 수와 같다.
int N = Integer.parseInt(br.readLine());
// DP 테이블 초기화
D = new int[N+1];
for(int i=0; i<=N; i++) {
D[i] = -1;
}
D[0] = 1;
D[1] = 1;
fibo(N);
bw.write(D[N]+"\n");
bw.close();
br.close();
}
static int fibo(int n) {
if(D[n] != -1) {
return D[n];
}
// N의 범위가 1,000,000까지 이므로 더할 때마다 15746으로 나눈다.
// fibo(N) 함수 수행 이후에만 나누면 안된다.
return D[n] = (fibo(n-1) + fibo(n-2)) % 15746;
}
}
|
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.
