G7490. 0 만들기

문제

제출 코드

• 사용 알고리즘 : BFS, 브루트포스

연산할 수가 최대 9를 넘지 않기에, 브루트포스로 모든 경우를 연산해도 시간초과 나지 않을것으로 생각하고 bfs로 모두 탐색하였다.

이전 숫자와 합치는 경우가 있어, 재귀로 풀이 시 직전 수에 대한 정보도 넘겨줘야 하는 문제.

package gold;

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

public class G7490_makeZero {
	static StringBuilder sb = new StringBuilder();
	static int N;

	// n:연산할 수, sum:누적된 연산결과, pre:직전에 연산한 수, str:누적연산결과
	static void makeZero(int n, int sum, int pre, String str) {
		if(n>N) {
			if(sum==0) sb.append(str+"\n");
			return;
		}

		int tmp = (Math.abs(pre)*10 + n) * (pre>0 ? 1 : -1); // 앞에 수와 합쳐 만들어진 수
		makeZero(n+1, sum-pre+tmp, tmp, str+" "+n); // 현재 수 붙이기

		makeZero(n+1, sum+n, n, str+"+"+n); // 현재 수 더하기
		makeZero(n+1, sum-n, -n, str+"-"+n); // 현재 수 빼기
	}

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

		for(int t=0; t<T; t++) {
			N = Integer.parseInt(br.readLine());
			if(t>0) sb.append("\n");
			makeZero(2, 1, 1, "1");
		}

		System.out.println(sb);
	}

}