0 만들기(BJ_G5_7490)

1. 문제 링크

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

7490번: 0 만들기

---

 

2. 나의 코드

메모리: 20208kb
시간: 252ms
코드 길이: 1929B
시간 복잡도 : O(3^N)
설명:N까지의 수까지 +, -, 공백 이렇게 3가지 경우를 모두 고려하여 dfs를 활용

import java.util.Scanner;

public class BJ_7490 {

    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        for (int T = 0; T < test; T++) {
            N = sc.nextInt();
            StringBuilder sb = new StringBuilder();
            sb.append(1);
            dfs(1, sb);
            System.out.println();
        }
    }

    public static void dfs(int num, StringBuilder sb) {
        if (num == N) {
            if (calc(sb) == 0) {
                System.out.println(sb);
            }
            return;
        }

        StringBuilder newSb = new StringBuilder(sb.toString());
        dfs(num + 1, newSb.append(" ").append(num + 1));
        newSb = new StringBuilder(sb.toString());
        dfs(num + 1, newSb.append("+").append(num + 1));
        newSb = new StringBuilder(sb.toString());
        dfs(num + 1, newSb.append("-").append(num + 1));
    }

    public static int calc(StringBuilder sb) {
        int num  = 0;
        int result = 0;
        char op = '+';
        String s = sb.toString();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '+') {
                if (op == '+') {
                    result += num;
                } else {
                    result -= num;
                }
                num = 0;
                op = '+';
            } else if (s.charAt(i) == '-') {
                if (op == '+') {
                    result += num;
                } else {
                    result -= num;
                }
                num = 0;
                op = '-';
            } else if ((s.charAt(i) == ' ')) {
                num *= 10;
            } else {
                num += (s.charAt(i) - '0');
            }
        }
        if (op == '+') {
            result += num;
        } else {
            result -= num;
        }
        return result;
    }
}

 

---

 

3. 정답 코드

import java.io.*;
import java.util.*;
import static java.util.stream.Collectors.toList;

public class Main {

	static int n;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int t = Integer.parseInt(br.readLine());
		while(t-- > 0) {
			n = Integer.parseInt(br.readLine());
			comb(1,1,"1");
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
	
	// +, -, ' '
	static void comb(int num, int len, String str){
		
		if(len == n) {
			if(calculate(str) == 0) {
				sb.append(str+"\n");
			}
			return;
		}
		
		comb(num+1, len+1, str+ ' ' + (num+1));
		comb(num+1, len+1, str+ '+' + (num+1));
		comb(num+1, len+1, str+ '-' + (num+1));
		
	}
	
	static int calculate(String str){
		str = str.replaceAll(" ", "");
		Iterator<Integer> it= Arrays.stream(str.split("[+,-]"))
				.map(Integer::parseInt)
				.collect(toList()).iterator();
		int result = it.next();
		for(int i=0; i<str.length(); i++) {
			if(str.charAt(i) == '+') {
				result += it.next();
			}else if(str.charAt(i) == '-') {
				result -= it.next();
			}
		}
		return result;
		
	}
}

 

---

 

4. 배운 점

- 재귀를 활용하는 방법까지는 어렵지 않았다. 하지만 공백일 경우 문자열들의 수식을 계산하는 과정에서 많은 시간을 소비했다. 다른 사람들은 계산 함수를 활용하지 않고 DFS에서 바로 계산을 하는 사람도 있다. 나도 그 부분을 더 공부해야 될 것 같다.