백준/9095번 :: 1, 2, 3 더하기 (Java 구현) DP - 다이나믹 프로그래밍

 

문제

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.

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

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

 

입력

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

 

출력

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

 

예제 입력2

3
4
7
10

 

예제 출력2

7
44
274

 

코드 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Ex9095 {

    private static int[] d; // n 수를 만들기 위한 경우의 수
    // d[n] = d[n-1] + d[n-2] + d[n-3]
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int test = Integer.parseInt(br.readLine());
            while(test-- > 0) {
                int n = Integer.parseInt(br.readLine());
                d = new int[n+1];
                for(int i=0; i< n+1; i++) {
                    if(i == 0) d[i] =0;
                    else if(i == 1) d[i] = 1;
                    else if(i == 2) d[i] = 2;
                    else if(i == 3) d[i] = d[i-1] + d[i-2] + 1;
                    else d[i] = d[i-1] + d[i-2] + d[i-3];
                }
                System.out.println(d[n]);
            }
        } catch (Exception e) {
            // TODO: handle exception
        }
    }
}​

 

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

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

 

관련 글

2018/05/02 - [Algorithm] - 알고리즘 :: 다이나믹 프로그래밍(DP) - 피보나치(Fibonacci) C/C++ 구현, 메모이제이션

2018/05/02 - [Algorithm/백준 온라인 저지] - 백준/11726번 :: 2xn 타일링 (C/C++ 구현)

2018/05/02 - [Algorithm/백준 온라인 저지] - 백준/11727번 :: 2xn 타일링 2 (C/C++ 구현)

2018/06/19 - [Algorithm/백준 온라인 저지] - 백준/11726번 :: 2xn 타일링 (Java 구현) - DP 다이나믹 프로그래밍

2018/06/19 - [Algorithm/백준 온라인 저지] - 백준/11727번 :: 2xn 타일링 2 (Java 구현) - DP 다이나믹 프로그래밍