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
6import 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();
}
}