4-5: Dessert

Dessert (Dessert.cpp)

 

문제

---

농부 존은 소들의 저녁식사 줄 세우는 새로운 방법을 개발 했다. N(1~15)마리의 소들을 순서대로 세 워놓은 후, 각 소들 사이에 +, - , . 셋 중 1가지가 써져있는 냅킨을 배치해서 최종 결과가 0 이 되게 해야 하는 것이다. 점(.)이 써져있는 냅킨을 통해 더 큰 수를 만들 수 있게 된다. 아래와 같은 경우를 보자. (ps .이 써져있는 냅킨은 '공백'이라고 생각하면 된다.)

1-2.3-4.5+6.7

이와 같은 배치는 1-23-45+67 을 나타낸다. 결과는 0 이다. 10.11은 1011 로 해석된다.

 

입력

---

첫 째 줄에는 소들의 수 N(1~15)이 입력된다.

 

출력

---

처음 20줄에 대해 가능한 20가지 답을 출력하는데, 사전 순으로 앞선 것을 출력한다. 순서는 +가 가장 앞서고 -와 . 이 순서대로 뒤따른다. 답이 20개 미만이면 가능한 답을 각 숫자와 문자 사이에 공백을 두고 출력한다. 모두 출력한다. 마지막 줄에는 가능한 답의 총 가지수를 출력한다.

 

예제 입력

7

예제 출력

1 + 2 - 3 + 4 - 5 - 6 + 7
1 + 2 - 3 - 4 + 5 + 6 - 7
1 - 2 + 3 + 4 - 5 + 6 - 7
1 - 2 - 3 - 4 - 5 + 6 + 7 
1 - 2 . 3 + 4 + 5 + 6 + 7 
1 - 2 . 3 - 4 . 5 + 6 . 7
6

import java.util.Scanner;

public class dessert {
    /**
     *
     * 농부 존은 소들의 저녁식사 줄 세우는 새로운 방법을 개발 했다.
     * N(1~15)마리의 소들을 순서대로 세 워놓은 후, 각 소들 사이에 +, - , . 셋 중 1가지가 써져있는 냅킨을 배치해서 최종 결과가 0 이 되게 해야 하는 것이다.
     * 점(.)이 써져있는 냅킨을 통해 더 큰 수를 만들 수 있게 된다. 아래와 같은 경우를 보자. (ps .이 써져있는 냅킨은 '공백'이라고 생각하면 된다.)
     *
     * 1-2.3-4.5+6.7
     * 1-23-45+67 을 나타낸다. 결과는 0 이다. 10.11은 1011 로 해석된다.
     *
     * 첫 째 줄에는 소들의 수 N이 입력된다.
     * 처음 20줄에 대해 가능한 20가지 답을 출력하는데, 사전 순으로 앞선 것을 출력한다.
     * 순서는 +가 가장 앞서고 -와 . 이 순서대로 뒤따른다. 답이 20개 미만이면 가능한 답을 각 숫자와 문자 사이에 공백을 두고 출력한다.
     * 모두 출력한다. 마지막 줄에는 가능한 답의 총 가지수를 출력한다
     *
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] numbers = new int[N];
        char[] combinations = new char[N];

        int[] count = new int[1];

        for (int i=0;i<N; i++){
            numbers[i] = i+1;
        }

        getZeroSums(count, numbers, combinations, 0, '+');

        System.out.println(count[0]);
    }

    private static void getZeroSums(int[] count, int[] numbers, char[] combinations, int index, char operand) {
        //current operand
        // if n, just add, since this is start
        if (index == numbers.length){
//            if (sum==0){
            if (computeSum(numbers, combinations) == 0){
                count[0]++;
                printArr(count, numbers, combinations);

            }
            return;
        }

        if (index ==0){
            combinations[0] = '+';
            getZeroSums(count,numbers, combinations, index+1,'+');
        } else {

            combinations[index] = '+';
            getZeroSums(count,numbers, combinations, index+1,'+');

            combinations[index] = '-';
            getZeroSums(count,numbers, combinations, index+1,'-');

            combinations[index] = '.';
            if (operand=='+'){
                getZeroSums(count,numbers, combinations, index+1,'+');
            } else if (operand == '-'){
                getZeroSums(count,numbers, combinations, index+1,'-');
            }

        }

    }

    private static int computeSum(int[] numbers, char[] combinations) {
        int sum = 0;
        StringBuilder sb = new StringBuilder();
        char prevOp = '+';
        int accum = 0;
        for (int i=0; i< numbers.length; i++){
            switch (combinations[i]){
                case '+':
                    sum += numbers[i];
                    accum = numbers[i];
                    prevOp = '+';
                    break;
                case '-':
                    sum -= numbers[i];
                    accum = numbers[i];
                    prevOp = '-';
                    break;
                case '.':
                    if (prevOp == '+'){
                        sum -= accum;
                        sum+= appendNums(accum, numbers[i]);
                        accum = appendNums(accum, numbers[i]);
                    } else if (prevOp =='-'){
                        sum += accum;
                        sum -= appendNums(accum, numbers[i]);
                        accum = appendNums(accum, numbers[i]);
                    } else {

                    }
                    break;
            }
            sb.append("curr sum: " + sum+"\n");

        }
        sb.append("finalsum: " + sum+"\n");
//        if (sum ==0) System.out.println(sb.toString());
        return sum;
    }

    private static int appendNums(int number, int number1) {
        int result = 0;
        if (number1< 10){
            result += 10*number + number1;
        } else {
            result += 100*number + number1;
        }

        return result;
    }

    private static void printArr(int[] count, int[] numbers, char[] combinations) {
        if (count[0] > 20){
            return;
        }
        System.out.print(numbers[0]);

        for (int i=1; i<numbers.length; i++){
            System.out.print(String.valueOf(" " + combinations[i]) + " " + String.valueOf(numbers[i]));
        }

        System.out.println();
    }
}