[백준] 0 만들기 (java) Recursion

2020-03-02

0 만들기 (백준> Recursion)

문제 링크

문제설명

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

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

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

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

예제 입력 1 복사

2
3
7

예제 출력 1 복사

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7


풀이

package Recursion;

import java.util.*;

//50min
public class beak_0만들기 {

	static int target = 0;
	
	//sum은 이번에 들어온 now에 부호 붙여주고 세번째 재귀때문에 now를 따로 만들어줘야했다
	//dfs(,, now*10 + (next+1)) 새로 들어온 now에 *10해주고 지금 있는 next+1 해줘야 22 이렇게 들어왔을때, 2*10 + (2+1) 가능 
	static void dfs(int sum,int sign, int num, int now, String c) {
		if(now == target) { // 기저조건 now가 target까지 왔을 때
			
			sum = sum + (num * sign); //내가 가진 sum과 이번에 들어온 num*sign이 0인지 확인한다
			if(sum == 0)
				System.out.println(c);
			return ;
		}

		dfs(sum, sign, num*10 + (now+1), now+1, c + " "+String.valueOf(now+1));
		dfs(sum + (sign* num), 1, now+1, now+1, c + "+" + String.valueOf(now+1));
		dfs(sum + (sign*num), -1, now+1, now+1, c + "-" + String.valueOf(now+1));

		
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		sc.nextLine();
		
		for(int i=0;i<n;i++) {
			target = sc.nextInt();
			String c = "1";
			
			dfs(0,1,1,1,c); // sum, sign, num, next, str
			
			System.out.println(" ");
		}
		
	}
}

후기 (50min)

타겟넘버랑 비슷한 문제였고… 변수들도 여러개 비슷하게 설정해주었으나, 나오는 숫자를 바로 string에 넣어서 보낼 생각은 하지 못했다. 좀 더 재귀에 익숙해져야겠다…