[알고리즘] 백준 9095번 1,2,3 더하기 Java 자바

www.acmicpc.net/problem/9095

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

public class Main {
    private static int []result;
    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());
        result=new int[t];
        for(int i=0;i<t;i++){
            result[i]=0;
            int n=Integer.parseInt(br.readLine());
            backtracking(n,i);
            System.out.println(result[i]);
        }

    }

    public static void backtracking(int n,int order){
        if(n==0){
            result[order]++;
        }

        for(int i=1;i<=3;i++){ //1,2,3
            int chk=n-i;
            if(chk>=0)
            backtracking(n-i,order);
        }

    }
}

 

백트래킹을 이용하여 풀었습니다.

1,2,3을  for문으로 돌려서 재귀함수로 자기자신을 호출하면서 정수가 0이되면 카운트하고 백트레킹이 끝난 후 결과값을 출력하였습니다.

 

제가 지금까지 백트래킹을 3~4문제정도 봤지만 체감 상 그나마 쉬운 편이여서 수월하게 풀어 냈습니다.