[Baekjoon] 7490_0 만들기

Gold V

문제(출처: https://www.acmicpc.net/problem/7490)

---

< 0 만들기 >

 

문제 풀이 

 

'+', '-', ' '을 넣을 수 있는 모든 경우의 수를 탐색한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class _7490_ { // 0 만들기
	static ArrayList<String> answer;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int t = Integer.parseInt(bf.readLine());
		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());

			String result = "1";
			answer = new ArrayList<>();
			search(result, n, 2);

			for(String str:answer) {
				bw.write(str+"\n");
			}
			bw.write("\n");
		}
		bw.flush();
	}

	private static void search(String result, int n, int idx) {
		if (idx == n + 1) {
			String temp = result.replace(" ", "");
			int x = 1;
			int a = temp.charAt(0) - '0';
			while (x < temp.length() && Character.isDigit(temp.charAt(x))) {
				a *= 10;
				a += temp.charAt(x++)-'0';
			}
			while (x < temp.length()) {
				int y = x;
				y += 1;
				int b = temp.charAt(y) - '0';
				while (y + 1 < temp.length() && Character.isDigit(temp.charAt(y + 1))) {
					b *= 10;
					b += temp.charAt(++y) - '0';
				}
				if (temp.charAt(x) == '+') {
					a += b;
				} else {
					a -= b;
				}
				x = y + 1;
			}
			if (a == 0) {
				answer.add(result);
			}
			return;
		}

		search(result + " " + idx, n, idx + 1);
		search(result + "+" + idx, n, idx + 1);
		search(result + "-" + idx, n, idx + 1);

	}
}

변수)
t : 테스트 케이스 개수
n : 자연수 N
result : 수식
answer : 0이 되는 수식

 

테스트 케이스 수 t를 입력받는다. 테스트 케이스 수만큼 자연수 N을 입력받아 search 함수를 호출한다. 최종 answer 값을 출력한다.

 

search(수식, 자연수 N, 현재 값)

현재 값이 n+1이라면 수식을 계산한다. 계산을 위해 공백을 제거한다. 먼저 값 a를 수식의 0번째 값으로 초기화한다. 숫자를 이어 붙인 것을 확인하기 위해 다음 값이 숫자인지 확인하며 숫자라면 이어 붙이고 숫자가 아니라면 다음 과정을 반복한다.

 

값 b를 수식의 y번째 값으로 초기화한다. 숫자를 이어 붙인 것을 확인하기 위해 다음 값이 숫자인지 확인하며 숫자라면 이어 붙인다. b값을 구한 뒤 x번째 값이 +라면 a와 b를 더하고, -라면 a와 b를 뺀다.

 

만약 결과가 0이라면 answer에 수식을 추가한 후 종료한다.

 

공백을 삽입하여 search 함수를 호출한다.

+를 삽입하여 search 함수를 호출한다.

-를 삽입하여 search 함수를 호출한다.

---

---