[백준] 7490. 0 만들기 - 골드5

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

7490번: 0 만들기

 

문제 요약

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

 

문제 해결 아이디어

여러 가지 생각을 해 봤다. 기본적인 아이디어는 어차피 숫자는 정해져 있으니까 그 사이에 들어갈 연산자만 뽑으면 된다는 것이다. 거기에 더해 백트래킹을 하려면 최대한 재귀를 덜 돌 수 있는 방법을 생각해 내야 했는데 그래서 재귀를 돌 때 res를 가지고 돌기로 생각했다.

물론 끝까지 다 뽑아 봐야 0이 되는지 안 되는지를 찾을 수 있었다. 중간에 쳐낼 방법은 끝내 생각지 못함.... ㄱ- 결국 res를 가지고 돌았던 건 다 뽑은 뒤에 for문 돌려서 하나하나 계산해 주지 않아도 되었기에 좋은 선택이었다.

뽑는 건 사실 그냥 세 개 중에 하나 뽑고 재귀를 돌리면 되는데 공백을 뽑았을 때 결과를 처리하는 부분이 어려워서... 출력을 위해 op 배열을 만들었지만 공백을 뽑았을 때 이전 결과로 돌아가게 만들기 위해 op 배열을 사용했다.

 

요약하자면

1. 공백, +, - 중에 하나 선택

2. 공백을 뽑으면 이전 부호를 체크해 줌. 

 2-1. 이전 부호가 +면 결과에 이전 숫자를 뺀다. (결과/res를 되돌린다)

 2-2. 이전 부호가 -면 결과에 이전 숫자를 더한다.

 2-3. 이전 부호가 공백이면 상관 X

3. 다음 부호를 뽑으러 부호에 따른 결과 값을 가지고 재귀를 돌려 준다.

4. 다 뽑으면 결과가 0일 때 출력. (StringBuilder에 append)

 

굳이 int[] arr 배열을 만들지 않았어도 될 것 같다. 어차피 숫자는 오름차순 배열이기 때문에...

 

 

완성된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	/*
	 * 84ms
	 */

	static int N;
	static int[] arr;
	static char[] op;
	static StringBuilder sb;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		sb = new StringBuilder();

		for (int testCase = 0; testCase < TC; testCase++) {
			N = Integer.parseInt(br.readLine());
			arr = new int[N];
			op = new char[N - 1];
			for (int i = 0; i < N; i++) {
				arr[i] = i + 1;
			}
			pick(0, 1);
			sb.append("\n");
		}
		System.out.println(sb);
	} // end of main

	public static void pick(int cnt, int res) {
		if (cnt == N - 1) {
			if (res == 0) {
				for (int i = 0; i < N - 1; i++) {
					sb.append(arr[i]).append(op[i]);
					// System.out.print(arr[i]);
					// System.out.print(op[i]);
				}
				sb.append(arr[N - 1]).append("\n");
				// System.out.println(arr[N - 1]);
			}
			return;
		}

		// +, -, 공백 중에 하나를 뽑아야 한다
		// 1부터 시작해서 첫번째 기호를 뽑을 때 cnt+1과 res 결과를 가지고 연산해 줌

		op[cnt] = ' ';
		if (cnt > 0 && op[cnt - 1] == '+') {
			pick(cnt + 1, res - arr[cnt] + (arr[cnt] * 10 + arr[cnt + 1]));
		} else if (cnt > 0 && op[cnt - 1] == '-') {
			pick(cnt + 1, res + arr[cnt] - (arr[cnt] * 10 + arr[cnt + 1]));
		} else {
			pick(cnt + 1, res * 10 + arr[cnt + 1]);
		}

		op[cnt] = '+';
		pick(cnt + 1, res + arr[cnt + 1]);

		op[cnt] = '-';
		pick(cnt + 1, res - arr[cnt + 1]);
	}
} // end of class