[백준] 1, 2, 3 더하기

문제 흐름

1. 문제 목표
   • 숫자 n이 주어졌을 때, 숫자 1, 2, 3을 사용해 그 합이 n이 되는 모든 경우의 수를 계산합니다.
2. 입력 및 출력 설명
   • 여러 테스트 케이스에 대해 각각의 숫자 n을 입력받고, 각 경우에 대해 결과를 출력합니다.

 

핵심 아이디어

• 동적 프로그래밍(DP)
  • 현재 숫자 i를 만들기 위해 마지막에 추가하는 숫자가 1, 2, 또는 3일 때의 경우를 합산합니다.
  • 점화식: arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
    • 여기서 arr[i]는 숫자 i를 만드는 경우의 수를 나타냅니다.
  • 이 문제는 미리 계산된 DP 배열에서 결과를 빠르게 조회하는 방식으로 해결할 수 있습니다.

 

알고리즘 흐름

1. DP 배열 초기화
   • arr[0]=1로 초기화합니다.
   • 배열을 통해 1부터 10까지의 결과를 미리 계산합니다.
2. DP 배열 채우기
   • 각 숫자 i를 이전 3개의 합을 통해 구합니다.
3. 결과 출력
   • 미리 계산된 DP 배열에서 주어진 숫자에 해당하는 값을 출력합니다.

 

 

---

정답은 더보기 클릭

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

public class Main {
	
	static int N; // 테스트 케이스 수
	
    public static void main(String[] args) throws IOException {
        
    	Scanner in = new Scanner(System.in);
    	
    	N = in.nextInt(); // 테스트 케이스 수 입력
    	
    	int[] arr = new int[11]; // DP 배열 선언, 최대 10까지 미리 계산
    	
    	arr[0] = 1; // 기본 초기화: 숫자 0을 만드는 방법은 1가지 (아무것도 선택하지 않는 경우)
    	
    	// DP 배열 채우기
    	for (int i = 1; i < 11; i++) {
    		int sum = 0;
    		
    		// 마지막에 더해지는 숫자가 1, 2, 3인 경우를 각각 추가
    		if (i >= 1) sum += arr[i - 1];
    		if (i >= 2) sum += arr[i - 2];
    		if (i >= 3) sum += arr[i - 3];
    		
    		arr[i] = sum; // i를 만드는 경우의 수 저장
    	}
    	
    	// 각 테스트 케이스에 대해 결과 출력
    	for (int i = 0; i < N; i++) {
    		System.out.println(arr[in.nextInt()]);
    	}
    }
}