[JAVA] 백준 9095번: 1, 2, 3 더하기

 

---

문제

• 정수 n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하는 문제.

 

아이디어

• 각 정수가 표현되는 경우의 수는 다음과 같다.
  • 1 (1가지): 1
  • 2 (2가지): 1+1, 2
  • 3 (4가지): 1+1+1, 1+2, 2+1, 3
  • 4 (7가지): 1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1
• 각 경우의 수를 계산해보면 정수 n은 n-3, n-2, n-1의 가지수를 모두 더한 것과 같다.
• 즉, 다음과 같은 점화식을 세울 수 있다.

$$a_{n} = a_{n-1} + a_{n-2} + a_{n-3}$$

• 배열을 선언하고, 해당 점화식을 구현한다.

 

풀이

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));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        int[] arr = new int[11];
        // 초기값 초기화
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 4;
        
        // 점화식 구현
        for(int i=4; i<11; i++) {
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        }

        for(int t=0; t<T; t++){
            int n = Integer.parseInt(br.readLine());
            sb.append(arr[n]).append('\n');
        }

        System.out.println(sb);
    }
}

 

 

채점 결과

9095번 채점 결과

 

문제 링크

• 9095번: 1, 2, 3 더하기 (acmicpc.net)