[코딩테스트/백준 알고리즘] 9095번 : 1, 2, 3 더하기 (자바, Java 풀이)

문제

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

---

문제 설명

---

문제 풀이

 정수 4를 1, 2, 3의 합으로 나타내는 방법을 보자

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 1 + 3
• 2 + 1 + 1
• 2 + 2
• 3 + 1

 이걸 좀 있어보이게 나타내면 아래 표와 같다. 어떻게 작은 문제로 나눠야 하는지 보일 것이다.

n	식	나타내는 방법
4	1 + (n - 1)	1 + (1 + 1 + 1)
		1 + (1 + 2)
		1 + (2 + 1)
		1 + 3
	2 + (n - 2)	2 + (1 + 1)
		2 + 2
	3 + (n - 3)	3 + 1

 n에서 1, 2, 3을 빼고 남은 수를 다시 1, 2, 3의 합으로 나타내면 n을 1, 2, 3으로 나타내는 방법의 수를 알아낼 수 있다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] memo = new int[11];
        memo[0] = 1;
        memo[1] = 1;
        
        /*정수 입력*/
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        /*1로 만드는 방법의 수 계산*/
        for(int i = 2; i <= 10; i++) {
            if(i == 2) {
                memo[i] = memo[i - 2] + memo[i - 1];
            }
            else {
                memo[i] = memo[i - 3] + memo[i - 2] + memo[i - 1];
            }
        }
        
        /*출력*/
        for(int i = 0; i < n; i++) {
            System.out.println(memo[arr[i]]);
        }
    }
}