[백준]7490: 0만들기(java)

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

7490번: 0 만들기

문제

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

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

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

입력

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

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

출력

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

예제 입력 1 

2
3
7

예제 출력 1 

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

---

풀이

1. 재귀적으로 +, -, ' '이 가능한 모든 경우의 수를 둬봅니다.

dfs(N, 1, new char[N]);

public static void dfs(int N, int cnt, char[] arr) {
    if(cnt==N) {
        if(result(arr, N)) {
            for(int i=1; i<=N; i++) {
                if(i!=N) {
                    ans.append(i).append(arr[i]);
                } else {
                    ans.append(i);
                }
            }
            ans.append('\n');
        }
        return;
    }

    arr[cnt] = ' ';
    dfs(N, cnt+1, arr);
    arr[cnt] = '+';
    dfs(N, cnt+1, arr);
    arr[cnt] = '-';
    dfs(N, cnt+1, arr);
}

- 우리는 ASCII 코드 순으로 정답을 출력해야하므로 ' ' > + > - 순으로 모든 경우의수를 찾습니다.

2. 경우의수 배열이 다 찾아졌다면 result 함수를 통해 누적 합이 0이 되는지 확인합니다.

public static boolean result(char[] arr, int N) {
    int sum = 0;
    for(int i=N; i>1; i--) {
        int num = i;
        if(arr[i-1] == '+') {
            sum+=num;
        } else if(arr[i-1] == '-') {
            sum-=num;
        } else {
            int result = i;
            int cnt = 1;
            while(arr[i-1] == ' ') {
                i--;
                result = i*(int)Math.pow(10, cnt++)+result;
            }
            if(i-1 >=1 && arr[i-1] == '-') {
                sum-=result;
            } else {
                sum+=result;
            }
        }
    }
    if(arr[1] != ' ') {
        sum+=1;
    }
    if(sum == 0) return true;
    else return false;
}

- 1 2 + 3 4 5 - 6 7인 경우

저는 뒤의 숫자부터 연산해주었습니다.

7 앞은 공백이므로 else에 들어갑니다.

공백을 만날때까지 앞의 숫자를 Math.pow(10, cnt++)을 곱해주며 더해나갑니다.

이 후에 맨 앞의 수가 아니면서 -인경우는 빼기 연산을 해주고

그외엔 다 +연산을 해줍니다.

이유 :  123 - 456을 생각해보면

sum에는 -456이 들어가지만 123은 무조건 +연산을 해줘야합니다.

모든 연산이 있고난 후에 맨 처음이 공백이 아니었다면(공백이면 이미 연산을 해줬음) 1을 더해줍니다.

이 후에 sum=0으로 true값이 반환되면 결과를 저장합니다.

 

전체코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BJ_G5_7490_0만들기 {
    static StringBuilder ans = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());
        for(int t=1; t<=TC; t++) {
            int N = Integer.parseInt(br.readLine());

            dfs(N, 1, new char[N]);
            ans.append('\n');
        }
        System.out.printf("%s", ans.toString());
    }

    public static void dfs(int N, int cnt, char[] arr) {
        if(cnt==N) {
            if(result(arr, N)) {
                for(int i=1; i<=N; i++) {
                    if(i!=N) {
                        ans.append(i).append(arr[i]);
                    } else {
                        ans.append(i);
                    }
                }
                ans.append('\n');
            }
            return;
        }

        arr[cnt] = ' ';
        dfs(N, cnt+1, arr);
        arr[cnt] = '+';
        dfs(N, cnt+1, arr);
        arr[cnt] = '-';
        dfs(N, cnt+1, arr);
    }

    public static boolean result(char[] arr, int N) {
        int sum = 0;
        for(int i=N; i>1; i--) {
            int num = i;
            if(arr[i-1] == '+') {
                sum+=num;
            } else if(arr[i-1] == '-') {
                sum-=num;
            } else {
                int result = i;
                int cnt = 1;
                while(arr[i-1] == ' ') {
                    i--;
                    result = i*(int)Math.pow(10, cnt++)+result;
                }
                if(i-1 >=1 && arr[i-1] == '-') {
                    sum-=result;
                } else {
                    sum+=result;
                }
            }
        }
        if(arr[1] != ' ') {
            sum+=1;
        }
        if(sum == 0) return true;
        else return false;
    }
}