백준9095

문제

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

출력

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

예제 입력1

3
4
7
10

예제 출력1

7
44
274

시도

보자마자 DFS로 접근하자는 생각을 했었다. 한번 지나갔던 경로에 대해서는 탐색하지 않으며, 해당 경로에 해당하는 값들의 합이 정수 n과 같아지면 해당 경로에 대한 탐색을 종료하는 방식으로 고민해 보았다.
접근은 비슷하게 맞았으나, 구현력의 부족으로 풀이에 성공하지 못하였다.

풀이

• 기본적인 DFS의 재귀함수 호출 방식으로 구현한다.
• 1, 2, 3을 이용해 더해가며 결과 값을 찾으므로, 1씩 더할때, 2씩 더할때, 3씩 더할때에 대해서 DFS를 진행한다.
• 더해지는 value의 값이 target보다 커지면 해당 경로는 세지 않는다.
• target==value이면 count를 1증가 시킨다.

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

public class Main![](https://velog.velcdn.com/images/saint6839/post/fd8230cc-5712-4ec0-b6aa-3b8c90783a91/image.png)
 {
    private static int count = 0;

    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());

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            count = 0;
            dfs(n, 0);
            sb.append(count + "\n");
        }
        System.out.println(sb);
    }


    private static void dfs(int target, int value) {
        if(target < value) {
            return;
        }
        if(target == value) {
            count++;
            return;
        }

        else {
            dfs(target, value + 1);
            dfs(target, value + 2);
            dfs(target, value + 3);
        }
    }
}