백준 7490 (0 만들기) - java

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

7490번: 0 만들기

문제 : 0 만들기

유형 : 백트랙킹

 

접근 

1. 숫자와 숫자 사이에 들어갈 연산자를 백트랙킹으로 구현한다.
2. 모든 연산자를 채웠을 때 연산을 진행하고 결과가 0일 경우 문자열을 출력한다.

백트랙킹

    static void travel(int cur,StringBuilder sb){
        if(cur == m){

            if(sum()){
                String tmp = makeResult(); // 모든 연산자를 채웠을 때 연산
                sb.append(tmp+"\n");
            }

            return;
        }

        for(int i=1;i<=3;i++){
            cal[cur] = i; // 1 -> ' '(공백) , 2 -> '+'(더하기) , 3 -> '-'(빼기)
            travel(cur+1,sb);
        }
    }

연산

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

public class Main {
    static int n = 0;
    static int m = 0;

    static int[] cal;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i=1;i<=n;i++){
            m = Integer.parseInt(br.readLine());
            cal = new int[m];

            travel(1,sb);
            sb.append("\n");
        }

        System.out.print(sb.toString());


        br.close();
    }

    static String makeResult(){
        StringBuilder sb = new StringBuilder();

        sb.append(1);

        for(int i=2;i<=m;i++){
            if(cal[i-1] == 2)
                sb.append('+');

            else if(cal[i-1] == 3)
                sb.append('-');

            else
                sb.append(' ');

            sb.append(i);
        }


        return sb.toString();
    }

    static void travel(int cur,StringBuilder sb){
        if(cur == m){

            if(sum()){
                String tmp = makeResult(); // 모든 연산자를 채웠을 때 연산
                sb.append(tmp+"\n");
            }

            return;
        }

        for(int i=1;i<=3;i++){
            cal[cur] = i; // 1 -> ' '(공백) , 2 -> '+'(더하기) , 3 -> '-'(빼기)
            travel(cur+1,sb);
        }
    }

    static boolean sum(){
        int result = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(1);

        for(int i=2;i<=m;i++){

            if(cal[i-1] == 2){
                stack.push(i); // +인경우 그대로 스택에 추가
            }

            else if(cal[i-1] == 3){
                stack.push(i*-1); // -인경우 부호를 반대로하여 추가
            }
            // 공백인경우
            else{
                int cur = stack.pop();
                cur = cur * 10;

                if(cur > 0)
                    cur += i;

                else{
                    cur -= i;
                }

                stack.push(cur);
            }
        }

        while(!stack.isEmpty()){
            result += stack.pop();
        }


        if(result == 0)
            return true;

        return false;
    }
}

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    static int[] cal;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i=1;i<=n;i++){
            m = Integer.parseInt(br.readLine());
            cal = new int[m];

            travel(1,sb);
            sb.append("\n");
        }

        System.out.print(sb.toString());


        br.close();
    }

    static String makeResult(){
        StringBuilder sb = new StringBuilder();

        sb.append(1);

        for(int i=2;i<=m;i++){
            if(cal[i-1] == 2)
                sb.append('+');

            else if(cal[i-1] == 3)
                sb.append('-');

            else
                sb.append(' ');

            sb.append(i);
        }


        return sb.toString();
    }

    static void travel(int cur,StringBuilder sb){
        if(cur == m){

            if(sum()){
                String tmp = makeResult(); // 모든 연산자를 채웠을 때 연산
                sb.append(tmp+"\n");
            }

            return;
        }

        for(int i=1;i<=3;i++){
            cal[cur] = i; // 1 -> ' '(공백) , 2 -> '+'(더하기) , 3 -> '-'(빼기)
            travel(cur+1,sb);
        }
    }

    static boolean sum(){
        int result = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(1);

        for(int i=2;i<=m;i++){

            if(cal[i-1] == 2){
                stack.push(i); // +인경우 그대로 스택에 추가
            }

            else if(cal[i-1] == 3){
                stack.push(i*-1); // -인경우 부호를 반대로하여 추가
            }
            // 공백인경우
            else{
                int cur = stack.pop();
                cur = cur * 10;

                if(cur > 0)
                    cur += i;

                else{
                    cur -= i;
                }

                stack.push(cur);
            }
        }

        while(!stack.isEmpty()){
            result += stack.pop();
        }


        if(result == 0)
            return true;

        return false;
    }
}