[백준] 15988 - 1,2,3 더하기 3 (JAVA)

1. 소요시간 : 7분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 2
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/15988
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 사고과정

타일링 문제와 비슷해서 우선 그려보기로 했다. 4를 그릴 때 쯤에 규칙을 찾았다. 사진을 보면 이해할 수 있을 것이다.

3. 풀이과정

달리 설명할게 없다.
dp[i]=dp[i-1]+dp[i-2]+dp[i-3] 이다.
왜냐라면 dp[i-1] 의 조합들에서 3을 더하고,
dp[i-2] 의 조합들에서 2를 더하고,
dp[i-1] 의 조합을에서 1을 더하면
dp[i]의 조합이 될 수 있기 때문이다.

그리고 테스트케이스가 있으므로 한 번 할 때마다 계속 구하는 형식이 아닌, 우선 1,000,000까지 다 구해 놓고 그때그때 필요할때마다 뽑아서 쓴다면 시간을 훨씬 절약할 수 있다.

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		
		
		long dp[]=new long[1000001];
		long mod=1000000009;
		dp[1]=1;
		dp[2]=2;
		dp[3]=4;
		for(int i=4;i<dp.length;i++) {
			dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%mod;
		}
		
		int t=Integer.parseInt(br.readLine());
		while(t-->0) {
			int n=Integer.parseInt(br.readLine());
			sb.append(dp[n]+"\n");
		}
		System.out.println(sb);
		
		
		
	}
}

5. 결과

6. 회고

다이나믹 프로그래밍은 실버 문제와 골드 문제의 gap이 좀 큰 것 같다. 실버문제는 어렵지 않게 푸는데 골드 5만 돼도 숨이 턱 막힌다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212