DP 연습중 ... 접근을 거의 다 했는데 뒷심 부족인가... ㅠ 다해놓고 구현 못함
1을 만드는 경우 dp[1] = (1) -> 1개
2를 만드는 경우 dp[2] = (2), (1, 1) -> 2개
3을 만드는 경우 dp[3] = (3), (1, 1, 1), (1, 2), (2, 1) -> 4개
4를 만드는 경우
dp[4]
1, 1, 1, 1
1, 1, 2
1, 2, 1
1, 3
2, 1, 1
2, 2
3, 1
1 + 3 ( 앞이 1일 때, 3을 만드는 경우의 수 ) -> 4개
2 + 2 ( 앞이 2일 때, 2를 만드는 경우의 수 ) -> 2개
3 + 1 ( 앞이 3일 때, 1을 만드는 경우의 수 ) -> 1개
dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int[] dp = new int[11];
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i = 4; i <= 10; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
for(int i = 0; i < t; i++) {
int n = sc.nextInt();
System.out.println(dp[n]);
}
}
}
'코딩테스트 > Baekjoon' 카테고리의 다른 글
[백준 9656] 돌 게임2 (DP) (0) | 2023.08.04 |
---|---|
[백준 2775] 부녀회장이 될테야 (DP) (0) | 2023.08.04 |
int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하는지 구하기 (0) | 2023.04.09 |
주어진 문자열에서 각 알파벳이 몇 번씩 나왔는지 구하기 (0) | 2023.04.08 |