[백준] 7490. 0 만들기 (자바 JAVA)

[ 문제 ]  [백준] 7490. 0 만들기 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/7490

7490번: 0 만들기

 

---

# 접근 방법 및 풀이 

 

• dfs 문제다.
• 문제 자체는 어렵지 않았는데 첫번째 풀이로 풀고 나서 다른사람 코드 찾아보니 dfs재귀로만 풀어서 다시 풀어봤다.
• 첫번째 풀이는 "+, -, 공백" 3가지를 하나씩 선택해가면서 N까지 String 식을 만들었다. 이때 식에 공백이 들어간 부분은 replaceAll로 공백을 ""로 변경했다.
• 1 2+3일 경우, 공백을 ""로 만들면 12+3이 되므로 합을 계산하기 편하다. cal이라는 함수로 합을 계산해서 합이 0일 경우 정답list에 넣어줬다.
• 두번째 풀이는 식을 따로 계산하는 cal함수 없이 dfs함수에 파라미터를 추가해서 String식을 만들어가면서 합까지 계산하는 방식 풀이다.
• 추가된 파라미터는 다음과 같다.
• idx = 1~N, num = 만든 숫자, sum = 총합, op = 더하기면 1 빼기면 -1, express = 만든 식
• 이때 sum은 1이 아니라, 공백연산일 경우 이전의 숫자와 합쳐서 새로운 숫자를 만들어주어야 하므로 0부터 시작한다. 
• 여기서 공백일 경우, 다음 파라미터로 넘길 num은 (현재num*10)+(num+1) 을 해주면 된다.
• ex) num = 1, (1*10) + (1+1) = 12가 다음에 넘길 num이 된다.
• idx가 N일 경우, 마지막 num은 sum에 연산을 해주지 않았으므로 연산을 해준다.
• 자세한건 코드참조

 

 

# 주의할 점 

 

• dfs 풀때 재귀로만 풀 수 있다면 재귀로 풀어보기
• " " 공백일 경우 값을 어떻게 계산할지 고민해보기
• StringTokenizer에서 +나 - 문자를 구분자로 끊을 때는 "+|-"이지만, split는 정규표현식으로 구분자 표현하므로 split("[\\+|-]") 이다.
• StringTokenizer에서 파라미터에 true를 주면, 구분자도 포함해서 token에 담는다.

 

JAVA 코드

첫번째 버전

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static List<String> ans;
	static String op[] = {"+", "-", " "};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for(int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(in.readLine());
			ans = new ArrayList<>();
			dfs(1, "1");
			Collections.sort(ans);
			for(String s : ans) {
				System.out.println(s);
			}
			System.out.println();
			
		}
	}
	
	
	private static void dfs(int num, String s) {
		if(num == N) {
			String express = s.replaceAll(" ", "");
			if(cal(express))
				ans.add(s);
			return;
		}
		
		for(int i = 0; i < 3; i++) {
			dfs(num+1, s+op[i]+Integer.toString(num+1));
		}
	}


	private static boolean cal(String express) {
		StringTokenizer st = new StringTokenizer(express, "-|+", true);
		int sum = Integer.parseInt(st.nextToken());
		while(st.hasMoreElements()) {
			String s = st.nextToken();
			if(s.equals("+")) {
				sum += Integer.parseInt(st.nextToken());
			}else {
				sum -= Integer.parseInt(st.nextToken());
			}
		}
		
		if(sum == 0)
			return true;
		return false;
	}
}

두번째 버전

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.List;

public class Main {
	static int N;
	static List<String> ans;
	static StringBuilder sb;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for(int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(in.readLine());
			sb = new StringBuilder();
			dfs(1, 1, 0, 1, "1");
			System.out.println(sb);
		}
	}
	
	
	private static void dfs(int idx, int num, int sum, int op, String express) {
		if(idx == N) {
			sum += (num*op);
			if(sum == 0)
				sb.append(express + "\n");
			return;
		}
		
		dfs(idx+1, num*10+(idx+1), sum, op, express+" "+Integer.toString(idx+1));
		dfs(idx+1, idx+1, sum+(num*op), 1, express+"+"+Integer.toString(idx+1));
		dfs(idx+1, idx+1, sum+(num*op), -1, express+"-"+Integer.toString(idx+1));	
	}

}

 

 

REVIEW

요즘 다시 꾸준함의 중요성을 느끼고있다. 하루에 한개라도 좋으니 감 잃지 않게 계속해서 학습하자!