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

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

9095번: 1, 2, 3 더하기

[문제]

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

• 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보다 작다.

[출력]

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

[예제 입력]

[풀이 과정] 

 전형적인 다이나믹 프로그래밍 기법을 사용하는 문제이다. 1, 2, 3 만 가지고 주어지는 수를 만들어야 하기 때문에 뒤에 더해야하는 n-1 / n-2 / n-3 까지만 고려하여 재귀 연산을 하면 된다.

 

1) dp 함수에 입력값을 준다.

2) 넘겨 받은 입력 값에 대하여 dp (n-1) dp (n-2 ) dp(n-3) 재귀연산을 하면서 n==0이 될때만 count를 해주고 n<0일때는 함수를 빠져나온다.

 

[코드]

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

//dp 1,2,3 더하기
public class Main {
     static  int count =0;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수


        while (T -->0){
            dp(Integer.parseInt(br.readLine()));
            sb.append(count).append("\n");
            count=0;
        }

        System.out.print(sb);
    }

    public static void dp(int n){

        if(n==0){ //연산이 완료 되었기때문에 +1을 해준다.
            count++;
        }else if (n<0){ //연산이 불가능하기때문에 뒤로 돌아간다.
            return ;
        }

        dp(n-1);
        dp(n-2);
        dp(n-3);

    }
}

[결과]