반응형
🚀 문제
https://www.acmicpc.net/problem/9095
🚀 접근 방법
DP 문제이다.
보면 이전 3개의 합과 같은 것을 볼 수 있다.
점화식
dp[i-1]+dp[i-2]+dp[i-3]
1 | 2 | 3 | 4 | 5 |
1 | 1+1 2 |
1+1+1 1+2 2+1 3 |
1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 |
1+1+1+1+1 1+1+1+2 1+1+2+1 1+2+1+1 1+2+2 1+1+3 1+3+1 2+1+1+1 2+1+2 2+2+1 2+3 3+1+1 3+2 |
1개 | 2개 | 4개 | 7개 | 13개 |
🚀 코드
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++){
int m = Integer.parseInt(br.readLine());
int[] dp = new int[m+1];
dp[1] = 1;
if(m>=2)
dp[2] = 2;
if(m>=3)
dp[3] = 4;
for(int j=4; j<=m; j++){
dp[j] = dp[j-1]+dp[j-2]+dp[j-3];
}
bw.write(dp[m]+"\n");
}
bw.flush();
br.close();
bw.close();
}
}
반응형
'코딩테스트' 카테고리의 다른 글
[백준-2579번] 계단 오르기 - Java (0) | 2025.06.03 |
---|---|
[백준-1904번] 01타일 풀이 - Java (0) | 2025.06.03 |
[백준-1463번] 1로 만들기 풀이 - Java (0) | 2025.06.03 |
[백준-14442번] 벽 부수고 이동하기 2 풀이 - Java (0) | 2025.06.03 |
[백준-1697번] 숨바꼭질 풀이 - Java (0) | 2025.06.03 |