[Java] 백준 15989. 1, 2, 3 더하기 4

정석·2024년 5월 31일

Java

알고리즘 학습

목록 보기

58/67

문제

💡문제 분석 요약

숫자 1,2,3 을 더해서 정수 n 을 만들 수 있는 경우의 수를 구해라

💡알고리즘 설계

초기 조건 설정: 주어진 작은 수들(1, 2, 3)에 대해 가능한 모든 경우의 수를 초기화
DP 배열 갱신: 각 숫자 i를 1, 2, 3의 합으로 나타내기 위해, i를 만들 수 있는 모든 방법을 작은 문제의 해를 이용하여 갱신
결과 출력: 입력된 각 숫자에 대해 dp 배열을 참조하여 결과를 출력

💡코드

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

public class Main {
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] dp = new int[100001][4];
		
		dp[1][1] = 1;
		dp[2][1] = 1;
		dp[2][2] = 1;
		dp[3][1] = 1;
		dp[3][2] = 1;
		dp[3][3] = 1;
		
		for (int i = 4; i < 100001; 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];
		}
		
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(br.readLine());
			System.out.println(dp[num][1] + dp[num][2] + dp[num][3]);
		}
	}
}

참고용 해설

DP 배열 초기화:

int[][] dp = new int[100001][4];를 통해 DP 배열을 선언합니다. 이 배열은 dp[i][j]로, i를 1, 2, 3의 합으로 나타내는 방법 중 마지막 항이 j인 경우의 수를 저장합니다.
초기 조건을 설정합니다.
- dp[1][1] = 1: 1을 마지막 항이 1로 끝나게 만드는 방법은 1가지입니다.
- dp[2][1] = 1: 2를 마지막 항이 1로 끝나게 만드는 방법은 1가지입니다. (1+1)
- dp[2][2] = 1: 2를 마지막 항이 2로 끝나게 만드는 방법은 1가지입니다. (2)
- dp[3][1] = 1: 3을 마지막 항이 1로 끝나게 만드는 방법은 1가지입니다. (1+1+1)
- dp[3][2] = 1: 3을 마지막 항이 2로 끝나게 만드는 방법은 1가지입니다. (1+2)
- dp[3][3] = 1: 3을 마지막 항이 3로 끝나게 만드는 방법은 1가지입니다. (3)

DP 배열 채우기:
- for (int i = 4; i < 100001; i++) 루프를 통해 4부터 100000까지의 수에 대해 DP 값을 채웁니다.
  - dp[i][1] = dp[i-1][1]: i를 마지막 항이 1로 끝나게 만드는 방법은 i-1을 마지막 항이 1로 끝나게 만든 후 1을 더하는 방법과 같습니다.
  - dp[i][2] = dp[i-2][1] + dp[i-2][2]: i를 마지막 항이 2로 끝나게 만드는 방법은 i-2를 마지막 항이 1 또는 2로 끝나게 만든 후 2를 더하는 방법과 같습니다.
  - dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]: i를 마지막 항이 3로 끝나게 만드는 방법은 i-3을 마지막 항이 1, 2, 3로 끝나게 만든 후 3을 더하는 방법과 같습니다.