[백준] 9095 1, 2, 3 더하기 - 자바(Java)

9095번

1, 2, 3 더하기

 

 

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

정수 n이 주어졌을 때,  n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

n은 양수이며 11보다 작다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합을로 나타내는 방법의 수를 출력한다.

 

 

 

 

 

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

9095번: 1, 2, 3 더하기

---

1. 작은 문제의 답을 구하여 규칙을 구한다

 

dp[1] = 1

dp[2] = 2

dp[3] = 4

dp[4] = 7

dp[5] = 13

...

 

dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 라는 식이 나온다.

 

 

 

이를 재귀함수를 이용한 Top-down 방식을 이용하여 나타내면,

import java.util.*;

public class B9095 {
    static Integer dp[];
    public static void main(String[] arg) {
        Scanner input = new Scanner(System.in);

        int max = input.nextInt();
        dp = new Integer[11];
        dp[0] = 0;

        for (int i = 0; i<max; i++) {
            int num = input.nextInt();

            System.out.println(count(num));

        }
    }
    public static int count(int n) {
        if (n == 1) {
            dp[n] = 1;
        }
        else if (n == 2) {
            dp[n] = 2;
        }
        else if (n == 3) {
            dp[n] = 4;
        }
        else if (dp[n] == null) {
            dp[n] = count(n-1) + count(n-2) + count(n-3);
        }
        return dp[n];
    }
}

와 같다.

 

 

 

 

tip) nullpointer 오류가 나지 않도록 dp의 0, 1, 2 등의 값을 초기화 해주어야 한다.