백준 7490번: 0 만들기

문제 설명

• https://www.acmicpc.net/problem/7490
• 1부터 N까지의 자연수를 순서대로 나열한 뒤 중간에 더하기, 빼기, 공백을 넣어 0이 되는 경우의 수를 구하는 문제입니다.

접근법

• 정해진 공식이 보이지 않고 N의 크기가 크지 않아 전체 경우의 수를 파악하는 방식으로 접근했습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static List<String> result; // 결과를 모아 정렬하기 위한 List

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			result = new LinkedList<String>();
			int N = sc.nextInt();
			subset(N, 2, "1"); // 완전탐색 실행
            
			Collections.sort(result); // 결과를 아스키 코드로 정렬
			for (int i = 0; i < result.size(); i++) {
				System.out.println(result.get(i));
			}
			System.out.println();
		}
	}

	public static void subset(int N, int depth, String str) {
		if (depth == N + 1) {
			if (calculate(str) == 0) {
				result.add(str);
			}
			return;
		}
		subset(N, depth + 1, str + "+" + Integer.toString(depth));
		subset(N, depth + 1, str + "-" + Integer.toString(depth));
		subset(N, depth + 1, str + " " + Integer.toString(depth));

	}

	public static int calculate(String s) {
		StringBuilder sb = new StringBuilder(); // 연속된 숫자들
		Deque<String> lst = new LinkedList<String>(); // 숫자들과 연산기호를 담은 리스트
        // lst에는 '1 2'가 들어있지 않고 12가 들어있습니다.
		for (int i = 0; i < s.length(); i++) {

			if (s.charAt(i) == '+' || s.charAt(i) == '-') { // 연산기호면
				lst.add(sb.toString()); // 지금까지 모은 연속된 숫자를 모두 lst에 삽입
				lst.add(Character.toString(s.charAt(i))); // 연산기호 lst에 삽입
				sb = new StringBuilder(); // 연속된 숫자 초기화
			} else if (s.charAt(i) == ' ') { // 빈칸이면
				continue; // 빈칸은 숫자가 아니기 때문에 연속된 숫자를 만드는 데 사용되지 않습니다.
			} else { // 숫자면
				sb.append(s.charAt(i)); // 연속된 숫자에 삽입
			}
		}
		lst.add(sb.toString()); // 마지막 숫자 삽입
        
		while (lst.size() != 1) { // 하나의 숫자만 남을때까지
        	// 연속된 숫자를 하나의 숫자로 삽입했기 때문에 lst 속에는 반드시 [숫자,연산기호,숫자,연산기호,숫자,...] 형태로 들어 있음
			int left = Integer.parseInt(lst.pollFirst()); // 왼쪽 숫자
			String oper = lst.pollFirst(); // 연산 기호 
			int right = Integer.parseInt(lst.pollFirst()); // 오른쪽 숫자
			if (oper.equals("+")) { // 더하기면
				lst.addFirst(Integer.toString(left + right)); // 왼쪽숫자와 오른쪽 숫자를 더해 왼쪽에 삽입
			} else if (oper.equals("-")) { // 빼기면
				lst.addFirst(Integer.toString(left - right)); // 왼쪽숫자에서 오른쪽 숫자를 빼 왼쪽에 삽입
			} else { // 공백이면
				lst.addFirst(Integer.toString(left * 10 + right)); // 왼쪽숫자 뒤에 오른쪽 숫자를 붙임
			}
		}
		return Integer.parseInt(lst.getFirst());
	}

}