https://www.acmicpc.net/problem/9461
p(n)의 규칙을 찾았다.
1 1 1 2 2 3 4 5 7 9 12 16 21 ...
p(n) = p(n-2) + p(n-3)이다.
처음에 dp테이블을 int로 풀었더니 n이 커지니까 음수가 나왔다. 수가 너무 커져서 int형의 범위를 벗어나서 그렇다. 그래서 dp테이블을 long으로 선언했다.
package com.ll;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static long[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++) {
int n = Integer.parseInt(br.readLine());
dp = new long[n+1];
System.out.println(p(n));
}
}
public static long p(int n) {
if(n <= 3) return dp[n] = 1;
if(dp[n] != 0) return dp[n];
return dp[n] = p(n-2) + p(n-3);
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static long[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
dp = new long[101];
for(int i = 1; i <= 100; i++) {
if(i <= 3) dp[i] = 1;
else dp[i] = dp[i-2] + dp[i-3];
}
for(int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
System.out.println(dp[N]);
}
}
}