백준 1812번 사탕 (JAVA)

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

1812번: 사탕

 

저는 dfs를 통해 문제를 해결하였습니다.

처음 것은 될 수 있는 만큼 캔디를 넣고, 그 다음 것은 앞의 캔디와 주어진 입력을 참조하여 값을 결정하였습니다.

마지막으로 마지막 뎁스까지 가면 마지막 입력값과 마지막 캔디 + 처음 캔디인지를 확인하여 문제를 해결하였습니다.

 

package BOJ.etc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.function.Function;

public class BOJ_1812 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        int[] candySum = new int[n];
        for(int i = 0 ; i < n ; i++){
            candySum[i] = stoi.apply(br.readLine());
        }
        int[] candy = new int[n];
        cal(0,candy,candySum,n);
        for(int i = 0 ; i < n ; i++){
            System.out.println(result[i]);
        }
    }
    public static int[] result = null;
    private static void cal(int depth,int[] candy, int[] candySum, int n) {
        if(depth >= n){
            if(candy[0] + candy[n-1] != candySum[n-1]){
                return;
            }
            result = Arrays.copyOf(candy,n);
            return;
        }
        if(depth == 0){
            for(int i = 0 ; i <= candySum[depth] ; i++){
                candy[depth] = i;
                if(candySum[n-1] - i < 0){
                    break;
                }
                candy[n-1] = candySum[n-1] - i;
                cal(depth+1,candy,candySum,n);
            }
        }else{
            int prevIndex = depth - 1;
            if(candySum[prevIndex] - candy[prevIndex] < 0){
                return;
            }
            candy[depth] = candySum[prevIndex] - candy[prevIndex];
            cal(depth+1,candy,candySum,n);
        }
    }
}