반응형
🔺 문제
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// dp 배열 채우기 (dp[x] : x 나타내는 방법 수)
int[][] dp = new int[10001][4];
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 = 4 ; i < dp.length ; i++) {
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];
}
// dp[입력 받은 값] 출력
int t = Integer.parseInt(br.readLine());
while(t --> 0) {
int n = Integer.parseInt(br.readLine());
int sum = dp[n][1] + dp[n][2] + dp[n][3];
System.out.println(sum);
}
}
}
|
cs |
✅ 해결 아이디어
✔ DP
- dp[ i ][ j ] : 임의의 정수 i가 j 로 끝남
다른 분들이 해설을 넘 잘 적어주셔서 그거 링크 남김,,,
🔺 다른 풀이들
- 해설 굿,,,ㅠ
💬 느낀 점
dp는 정말.. 재능의 영역인 것 같다...ㅎ
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
✔ 풀이 참고.. 과정 설명 짱...
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 24416번: 알고리즘 수업 - 피보나치 수 1 (0) | 2023.05.30 |
---|---|
[백준/JAVA] 1495번: 기타리스트 (0) | 2023.05.30 |
[백준/JAVA] 15988번: 1, 2, 3 더하기 3 (0) | 2023.05.29 |
[백준/JAVA] 12101번: 1, 2, 3 더하기 2 (0) | 2023.05.29 |
[백준/JAVA] 9095번: 1, 2, 3 더하기 (0) | 2023.05.28 |