소들의 줄세우기

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이 입력된다.

 

출력

---

처음 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.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static ArrayList<String[]> box = new ArrayList<>();

    public static String[] zz = {"1", "-", "2" ,".","3", "+", "4", "+", "5", "+", "6", "+", "7" };
    public static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b = 1;
        int c = 0;

        a = sc.nextInt();

        String[] x = new String[(2*a)-1];

        for(int i = 0 ; i < x.length ; i = i+2) {
            x[i]  = String.valueOf(b);
            b++;
        }

        dessert(x,0,a-1);
        System.out.println(count);
    }

    public static void dessert(String[] input,int a, int max) {

        if(a == max) {
            if(operationSum(input) == 0) {
                count++;
                if(count <= 20)printString(input);
            }
        }else {
            input[(2*a)+1] = "+";
            dessert(input,a+1,max);
            input[(2*a)+1] = "-";
            dessert(input,a+1,max);
            input[(2*a)+1] = ".";
            dessert(input,a+1,max);
        }
    }

    public static void printString(String[] input) {

        for(int i = 0 ; i < input.length; i++) {
            System.out.print(input[i]+" ");
        }
        System.out.println("");
    }

    public static String[] deepcopy(String[] input) {
        String[] result = new String[input.length];

        for(int i = 0 ; i < input.length; i++) {
            result[i] = input[i];
        }
        return result;
    }

    public static int operationSum(String[] in) {

        //ex 1 + 2 - 3 + 4 - 5 - 6 + 7
        int sum = 0;
        int plus = 0;
        String operation = "+";
        String[] input = deepcopy(in);

        // 처리
        for(int i = 0; i < input.length; i++) {
            String z = input[i];
            if(z.equals(".")) {
                int a = Integer.parseInt(input[i-1]);
                input[i-1] = "0";
                if(Integer.parseInt(input[i+1]) < 10) {
                    input[i+1] = String.valueOf(a*10 + Integer.parseInt(input[i+1]));
                }else {
                    input[i+1] = String.valueOf(a*100 + Integer.parseInt(input[i+1]));
                }
                input[i] = operation;
            }else if(z.equals("+") || z.equals("-")) {
                operation = z;
            }
        }
        operation = "+";


        for(int i = 0; i < input.length; i++) {
            String z = input[i];
            switch (z) {
                case "+" :
                    operation = z;
                    break;
                case "-" :
                    operation = z;
                    break;
                default:
                    plus = Integer.parseInt(z);
                    if(operation.equals("+")) sum = sum+plus;
                    else if(operation.equals("-")) sum = sum-plus;
            }
        }

        return sum;
    }

}