https://www.acmicpc.net/problem/15989
15989번: 1, 2, 3 더하기 4
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2
www.acmicpc.net
해당 문제를 DP를 이용하여 문제를 해결하였습니다.
1차원 DP를 이용하게 되면 중복이 발생하여 2차원 DP를 이용하였습니다.
저는 dp[표현하고자 하는 숫자][계산 중 최대로 작은 숫자]를 이용해 문제를 해결하였습니다.
dp[i][1] = dp[i-1][1];
dp[i][2] = dp[i-2][1] + dp[i-2][2];
dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3];
package BOJ.DP;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;
public class BOJ_15989 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Function<String,Integer> stoi = Integer::parseInt;
int n = stoi.apply(br.readLine());
int[][] dp = new int[10_000+1][4];
for(int i = 0 ; i <= 10_000; i++){
Arrays.fill(dp[i],-1);
}
dp[1][1] = 1;
dp[1][2] = 0;
dp[1][3] = 0;
dp[2][1] = 1;
dp[2][2] = 1;
dp[2][3] = 0;
dp[3][1] = 1;
dp[3][2] = 1;
dp[3][3] = 1;
for(int i = 0 ; i < n ; i++){
int num = stoi.apply(br.readLine());
int result = 0;
for(int j = 1 ; j <= 3; j++){
result += cal(dp,num,j);
}
System.out.println(result);
}
}
private static int cal(int[][] dp, int num, int start) {
if(dp[num][start] != -1){
return dp[num][start];
}
dp[num][start] = 0;
for(int i = 1 ; i <= start ; i++){
dp[num][start] += cal(dp,num-start,i);
}
return dp[num][start];
}
}