반응형

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public void solution() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int count = Integer.parseInt(br.readLine()); int[] num = new int[11]; num[1] = 1; num[2] = 2; num[3] = 4; for(int j = 4; j<=10; j++){ num[j] = num[j-3] + num[j-2] + num[j-1]; } for(int i = 0; i<count; i++){ sb.append(num[Integer.parseInt(br.readLine())]).append("\n"); } System.out.println(sb); } public static void main(String args[]) throws IOException { new Main().solution(); } }
DP(Dynamic programming)의 맛을 처음 보았다. 작은 문제부터 해결해나가면서 점차 범위를 넓혀나가는 상향식 접근법으로 풀이 해야한다. DP문제는 결국 규칙을 찾아내는게 중요한 것 같다.
풀이결론
dp[n] = dp[n-1] + dp[n-2] + dp[n-3] // n >= 4
숫자 4의 경우 1,2,3의 경우의 수의 합이 4의 경우의 수라는 규칙이 존재한다.
만약 숫자가 5라면, 2,3,4의 경우의 수의 합이 5의 경우의 수다.
이 규칙을 활용해 점화식으로 풀면 된다.
반응형
'개발 > 알고리즘' 카테고리의 다른 글
백준 15650번 : N과 M (2) (0) | 2023.01.04 |
---|---|
백준 15649번 : N과 M (1) (0) | 2023.01.04 |
백준 6064번 : 카잉 달력 (0) | 2023.01.02 |
백준 1107번 : 리모컨 (0) | 2023.01.02 |
백준 14500번 : 테트로미노 (0) | 2023.01.02 |