728x90
300x250
dp배열에 1,2,3의 합으로 나타내는 방법의 수를 넣어놓고
꺼내서쓴다.
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
public static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 0; t < T; t++) {
int n = sc.nextInt();
dp = new int[12];
// dp배열은 n을 1,2,3의 합으로 나타내는 방법의 수 출력
dp[1] = 1; // 1
dp[2] = 2; // 1+1 , 2
dp[3] = 4; // 1+1+1, 1+2, 2+1, 3
for (int i = 4; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];// +1했을 경우, +2했을 경우, +3했을 경우
}
System.out.println(dp[n]);
}
}
}
728x90
'알고리즘 > DP' 카테고리의 다른 글
백준 11057번: 오르막 수 [DP] - Java (0) | 2020.09.21 |
---|---|
백준 10844번: 쉬운 계단 수 [DP] - Java (0) | 2020.09.17 |
백준 1003번: 피보나치 함수 [DP] - Java (0) | 2020.09.16 |
피보나치 수 - [DP] - Java (0) | 2020.09.13 |
백준 12852번: 1로 만들기 2 [DP] - Java (0) | 2020.09.12 |