[백준_7490번] 0 만들기

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

7490번: 0 만들기

[문제]

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

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

 

[입력 조건]

• 첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).
• 각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

 

[코드]

import java.util.*;

public class BaekJoon_7490 {
	static int n;
	static int[] num;
	static StringBuilder sb;
	static String[] operation= {"+","-"," "};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		
		while(t-->0) {
			n=sc.nextInt();
			sb=new StringBuilder();
			
			DFS(1,1,0,1,"1");
			System.out.println(sb);
		}
	}
	
	// 재귀 깊이, 만든 숫자, 합계, 선택한 연산(+/-), 만들어진 식 
	static void DFS(int depth, int num, int sum, int op, String str) {
		if(depth==n) {
			sum+=(num*op); // 마지막 숫자 계산
			if(sum==0)
				sb.append(str).append("\n");
			
			return;
				
		}
		
		// 위에서부터 공백, +, - 순서
		DFS(depth+1,(num*10)+depth+1,sum,op,str+" "+Integer.toString(depth+1));
		DFS(depth+1,depth+1,sum+(num*op),1,str+"+"+Integer.toString(depth+1));
		DFS(depth+1,depth+1,sum+(num*op),-1,str+"-"+Integer.toString(depth+1));
	}
}

 

[고찰]

 이번 문제는 DFS 알고리즘을 사용하는 대표적인 문제였다. 선택할 수 있는 경우의 수가 공백, +, - 세가지 이기 때문에 각각의 경우마다 재귀함수를 호출해주었다. 재귀의 깊이가 n이 되었을 때, 아직 마지막 숫자가 연산되지 않았다는 점을 주의해야 했다.