[BaekJoon] 백준 7290번 _ 0 만들기 for JAVA

 

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

7490번: 0 만들기

 

 

문제

 

 

---

 

 

생각보다 어려웠던 문제였다.

 

 

N이 9까지밖에 없어서 수식을 만드는건 완탐인게 자명한데

 

 

띄어쓰기일 때 숫자를 붙여야해서 굉장히 헷갈렸다.

 

 

그래서 ArrayList 써서 붙이기로함

 

 

로직

1. 완탐으로 ' ', '+', '-'를 N-1개 뽑는다.

    -> 백트래킹 사용

2. 숫자랑 연산자를 저장할 ArrayList를 각각 선언함

3. for문으로 연산자를 훑으면서 1은 숫자리스트에 미리 넣어놓고 그 다음부터 연산자와 숫자를 보면서 각자 리스트에 넣음

    - ' '일 때는 숫자 리스트에서 빼서 붙이고 다시 집어넣음

4. 숫자와 연산자 계산해서 0이 되는지 확인

 

 

 

 

코드

import java.util.*;
import java.io.*;

public class Main {
    
    static int N;
    static char[] chr = {' ', '+', '-'};
    static char[] op;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=0; tc<T; tc++) {
            N = Integer.parseInt(br.readLine());
            op = new char[N-1];

            dfs(0);
            System.out.println();
        }

    }
    private static void dfs(int cnt) {
        if(cnt == N-1) {
            ArrayList<Integer> num = new ArrayList<>();
            ArrayList<Character> oper = new ArrayList<>();
            num.add(1);
            
            for(int i=0; i<N-1; i++) {
                //0:공, 1:+, 2:-
                if(op[i]==' ') {
                	int pre = num.get(num.size()-1);
                	num.remove(num.size()-1);
                	int now = pre*10 + (i+2);
                	num.add(now);
                }
                else if(op[i]=='+') {
                    oper.add('+');
                    num.add(i+2);
                }
                else {
                    oper.add('-');
                    num.add(i+2);
                }
            }
            int answer = num.get(0);
            for(int i=0; i<oper.size(); i++) {
            	if(oper.get(i) == '+')
            		answer += num.get(i+1);
            	else
            		answer -= num.get(i+1);
            }
            if(answer == 0) {
            	System.out.print("1");
            	for(int i=2; i<=N; i++) {
            		System.out.print(op[i-2] + ""+i);
            	}
            	System.out.println();
            }
            return;
        }
        for(int i=0; i<3; i++) {
            op[cnt] = chr[i];  
            dfs(cnt+1);
        }
    }

}

 

 

성능