[백준 알고리즘]7490번 자바(Java) 0 만들기

문제

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

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

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

 

입력

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

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

출력

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

 

풀이

• 시간복잡도
  • 3의 8제곱, 즉 1개의 케이스당 최대 약 6천
  • 근데 이제 케이스의 최대 개수 10, 케이스당 최대 8반복(calculateStr)
  • 6천x10x8 = 160만 예상
• 과정
  
  • 공백, +, - 순으로 문자열에 문자를 추가해줬다
  • 이후에 완성된 문자열은 계산시 0이맞는지 확인하는 calculateStr 검증 메서드로 들어가게된다.
  • 완성되지않은 문자열은 계속해서 공백, +, - 3가지를 진행하도록 한다

 

예제 입력 예시

2
3
7

 

예제 출력 예시

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

 

소스코드

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

//7490번 0 만들기
//공백경우, 0경우, 1경우 각각 구하기   순서: 공백, +, - 순

public class P7490 {
    private static StringBuilder sb;
    private static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        sb = new StringBuilder();

        while(T>0){
            n = Integer.parseInt(br.readLine());

            String str = "1";
            addGapPlusMinus(str, 2);
            sb.append("\n");

            T--;
        }
        System.out.println(sb);
    }

    static void addGap(String str, int temp){
        str = str+" "+temp;
        //현재 수가 n과 같으면 이제는 계산진행
        if(temp == n) calculateStr(str);
        else addGapPlusMinus(str, ++temp);
    }

    static void addPlus(String str, int temp){
        str = str+"+"+temp;
        if(temp == n) calculateStr(str);
        else addGapPlusMinus(str, ++temp);
    }

    static void addMinus(String str, int temp){
        str = str+"-"+temp;
        if(temp == n)calculateStr(str);
        else addGapPlusMinus(str, ++temp);
    }

    //Gap, Plus, Minus 3개 메서드 진행하는 메서드
    static void addGapPlusMinus(String str, int temp){
        addGap(str, temp);
        addPlus(str, temp);
        addMinus(str, temp);
    }

    //addGapPlusMinus를 통해 완성된 문자열 -> 계산을 통해서 0인지 확인 -> 0이면 문자열 append
    static void calculateStr(String str) {
        String tempStr = "1";
        char tempChar = '+';
        int sum = 0;

        for (int i = 2; i < n * 2; i += 2) {
            if (str.charAt(i - 1) == ' ') tempStr+=str.charAt(i);
            else{
                if(tempChar == '+')sum += Integer.parseInt(tempStr);
                else sum -= Integer.parseInt(tempStr);
                //초기화
                tempChar = str.charAt(i-1);
                tempStr = ""+str.charAt(i);
            }
        }

        //'tempChar'기준 마지막 수 + 또는 -
        if(tempChar == '+') sum += Integer.parseInt(tempStr);
        else sum -= Integer.parseInt(tempStr);

        if (sum == 0) sb.append(str).append("\n");
    }
}

 

 

 

 

문제 출처

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

7490번: 0 만들기