[Gold V] 0 만들기 - 7490

문제 링크

성능 요약

메모리: 18000 KB, 시간: 192 ms

분류

백트래킹, 브루트포스 알고리즘, 구현, 문자열

제출 일자

2024년 1월 5일 17:37:24

문제 설명

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

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

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

입력

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

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

출력

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

미완성 시도 코드

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

public class baekjoon_7490 {
	static int num;
	static boolean[] visited= new boolean[10];
    static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		for(int i=0; i<n; i++) {
			num=Integer.parseInt(br.readLine());
			dfs(2,1,"1");
            sb.append("\n");
		}
        System.out.println(sb.toString());
	}
	public static void dfs(int cnt,int sum,String s) {
		if(cnt==num+1) {
			if(sum==0) {
				sb.append(s+"\n");
			}
			return;
		}
		for(int i=cnt; i<=num; i++) {
			if(visited[i]) {
				continue;
			}
			visited[i]=true;
			dfs(cnt+1,sum+i,s+"+"+Integer.toString(i));
			//빈칸 구현 실패
			dfs(cnt+1,sum-i,s+"-"+Integer.toString(i));
			visited[i]=false;
		}
	}

}

+,- 까지는 구현했지만 빈칸을 구현하지 못해서 구글링으로 수정했다.

바꾼 코드

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

public class Main {
	static int ans;
	static StringBuilder sb = new StringBuilder();
	//static boolean[] visited= new boolean[10];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		for(int i=0; i<n; i++) {
			ans=Integer.parseInt(br.readLine());
			dfs(1,1,1,0,"1");
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
	
	public static void dfs(int cnt,int num,int option,int sum,String s) {
		if(cnt==ans) {
			sum +=num*option;
			if(sum==0) {
				sb.append(s+"\n");
			}
			return;
		}
		dfs(cnt+1,num*10+(cnt+1),option,sum,s+" "+String.valueOf(cnt+1));
		dfs(cnt+1,cnt+1,1,sum+(num*option),s+"+"+String.valueOf(cnt+1));
		dfs(cnt+1,cnt+1,-1,sum+(num*option),s+"-"+String.valueOf(cnt+1));
	}

}

[코드 참고 출처] 를 참고해 수정했다.