백트래킹/Dessert USACO 2002 poj 1950

알고리즘 종류 : 백트랙킹

---

Dessert

제한시간	메모리 제한
1000ms	32 MB

 

농부 존은 소들의 저녁식사 줄 세우는 새로운 방법을 개발 했다.

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

 

---

public class Main {
	private int totalCnt = 0;

	public static void main(String[] args) throws Exception {
		Main main = new Main();
		main.run();
		
	}
	
	private void run() throws Exception {
		System.setIn(new FileInputStream("src/test/input.txt"));
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String[] numbersAndOpts = new String[2 * N - 1];
		numbersAndOpts[0] = "1";
		fullSearch(numbersAndOpts, 2, 1, 2 * N - 1);
		System.out.println(totalCnt);
	}


	private void fullSearch(String[] numbersAndOpts, int cur, int idx, int maxIdx) {
		if (idx >= maxIdx) {
			if (checkEquationIsZero(numbersAndOpts)) {
				totalCnt++;
				if(totalCnt <= 30) printEquation(numbersAndOpts);
			}
			return;
		}

		numbersAndOpts[idx] = "+";
		numbersAndOpts[idx + 1] = Integer.toString(cur);
		;
		fullSearch(numbersAndOpts, cur + 1, idx + 2, maxIdx);

		numbersAndOpts[idx] = "-";
		numbersAndOpts[idx + 1] = Integer.toString(cur);
		;
		fullSearch(numbersAndOpts, cur + 1, idx + 2, maxIdx);

		numbersAndOpts[idx] = ".";
		numbersAndOpts[idx + 1] = Integer.toString(cur);
		;
		fullSearch(numbersAndOpts, cur + 1, idx + 2, maxIdx);
		
	}

	private Boolean checkEquationIsZero(String[] numbersAndOpts) {
		StringBuilder sb = new StringBuilder();
		
		int nextIdx = getNumberStr(numbersAndOpts, sb, 0);
		Double sum = Double.parseDouble(sb.toString());
		emptyStringBuilder(sb);
		while (nextIdx < numbersAndOpts.length) {
			
			if (numbersAndOpts[nextIdx].equals("+")) {
				nextIdx = getNumberStr(numbersAndOpts, sb, nextIdx + 1);
				sum += Double.parseDouble(sb.toString());
				emptyStringBuilder(sb);
					
			} else if (numbersAndOpts[nextIdx].equals("-")) {
				nextIdx = getNumberStr(numbersAndOpts, sb, nextIdx + 1);
				sum -= Double.parseDouble(sb.toString());
				emptyStringBuilder(sb);
			}
		}

		return sum.equals(0.0) ? Boolean.TRUE : Boolean.FALSE;
		// Double.parseDouble();
	}
	private void emptyStringBuilder(StringBuilder sb) {
		sb.setLength(0);
	}

	private int getNumberStr(String[] numbersAndOpts, StringBuilder sb, int cur) {
		sb.append(numbersAndOpts[cur]);
		int i = cur + 1;
		while(i < numbersAndOpts.length - 1 && numbersAndOpts[i].equals(".")) {
			sb.append(numbersAndOpts[i + 1]);
			i += 2;
		}
		return i;
	}
	
	private void printEquation(String[] numbersAndOpts) {
		for (int i = 0; i < numbersAndOpts.length; i++) {
			System.out.print(numbersAndOpts[i] + " ");
		}
		System.out.println("");
	}

	private void test() {
		String[] numbersAndOpts = {"1",".","2",".","3",".","4"};
		StringBuilder sb = new StringBuilder();
		System.out.println(getNumberStr(numbersAndOpts, sb, 0));
	}
	
	private void testCheckEquationIsZero() {
		String[] numbersAndOpts = {"1",".","2","-","1",".","2"};
		System.out.println(checkEquationIsZero(numbersAndOpts));
	}
	
	private String[] deepClone(String[] numbersAndOpts) {
		String[] copy = new String[numbersAndOpts.length];
		for (int i = 0; i < numbersAndOpts.length; i++) {
			copy[i] = numbersAndOpts[i];
		}
		return copy;
	}

	

	private void start() {
		String[] my = new String[10];
		my[0] = "hi";

		System.out.println("=====Array========");
		System.out.println(my[0]);

		changeContents(my);

		System.out.println(my[0]);

		System.out.println("=====Wrapper========");

		Integer num = new Integer(3);

		System.out.println(num);
		changeNumber(num);
		System.out.println(num);

		System.out.println("========Object===========");
		Obj obj = new Obj();
		obj.num = 3;

		System.out.println(obj.num);
		changeObj(obj);
		System.out.println(obj.num);

		System.out.println("==========Collection - List ==============");
		List<Integer> li = new ArrayList<>();
		System.out.println(li.size());
		changeList(li);
		System.out.println(li.size());

	}

	class Obj {
		public int num;
	}

	private void changeContents(String[] args) {
		args[0] = "test1";
		args[1] = "test2";
	}

	private void changeNumber(Integer num) {
		num = 13;
	}

	private void changeObj(Obj obj) {
		obj.num = 13;
	}

	private void changeList(List<Integer> li) {
		li.add(3);
	}
}

 

---

출처

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=463&sca=9040