[백준 14888번] 자바 연산자 끼워넣기 lv > silver1

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

14888번: 연산자 끼워넣기

 

 

문제 설명

예제 입력 1 복사

2
5 6
0 0 1 0

예제 출력 1 복사

30
30

예제 입력 2 복사

3
3 4 5
1 0 1 0

예제 출력 2 복사

35
17

예제 입력 3 복사

6
1 2 3 4 5 6
2 1 1 1

예제 출력 3 복사

54
-24

힌트

세 번째 예제의 경우에 다음과 같은 식이 최댓값/최솟값이 나온다.

• 최댓값: 1-2÷3+4+5×6
• 최솟값: 1+2+3÷4-5×6

 

문제 해석

문제 설명 중 빨간 색으로 밑 줄 친 곳이 중요하다..!! 연산자의 우선 순위 상관없이 앞에서부터 진행!! 언제나 문제에 답이 있다는 것을 기억하자!

 

왜 저 말이 중요하냐? dfs 사용을 할 수 있기 때문이다.

 

예를 들어 짧은 숫자들로 생각을 해보자

ex> 2 1 7 이라는 숫자가 들어왔을때 첫번째 숫자인 2를 무조건 앞에 두고 뒤에 두번째 숫자인 1을 + 더할지, - 뺄지, * 곱할지, / 나눌지 연산자의 개수에 맞게 경우의 수가 존재한다. 앞의 숫자와 뒤에 숫자 사이에 어떤 연산자를 사용할지 쉽게 말해서 일일히 다 대입하는 경우의 수를 찾아야 하는 문제인 것이다!

그럼 이 문제는 쉽다. 

 

* 구현 로직 *

1. 첫번째줄에 숫자의 개수인 N을 입력받는다.

2. N만큼의 숫자 배열을 만들고 나서 차례대로 입력을 받아 배열을 채운다.

4. 연산자는 + - * / 순서이고 해당 순서에 연산자의 개수를 입력받는다. 즉 길이가 4개인 연산자 배열을 만든 뒤 2번처럼 차례로 숫자를 입력 받는다.

5. 이제 계산을 일일히 해줘야하는데 이때 우린 최솟값과 최댓값을 구해야하니 최소값 변수와 최대값 변수를 만들어야한다.

6. 첫번째 숫자를 넣고 그 다음 숫자 인덱스를 넣고 dfs를 진행한다.

7. 연산자가 있는 경우(연산자의 개수가 0이상일 경우) 일단 계산을 하는 dfs를 만든다.

8. 숫자 인덱스가 N일 경우, 즉 다음 숫자가 없는 경우 dfs를 종류한다. 종류하기 전에 최댓값과 최솟값을 구한다.

 

코드

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

public class BJ14888{

    static int N;
    static int[] numbers;
    static int[] operators;
    static int MinResult = Integer.MAX_VALUE;
    static int MaxResult = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        numbers = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        operators = new int[4];  // operators[0]: + 개수,  operators[1]: - 개수, operators[2]: X 개수, operators[3]: / 개수
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i ++) {
            operators[i] = Integer.parseInt(st.nextToken());
        }
        dfs(numbers[0], 1);
        System.out.println(MaxResult);
        System.out.println(MinResult);
    }
    
    public static void dfs(int num, int idx) {
        if (idx == N){
            MaxResult = Math.max(num, MaxResult);
            MinResult = Math.min(num, MinResult);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (operators[i] > 0) {
                operators[i]--;

                switch (i) {
                    case 0 :
                       dfs(num + numbers[idx], idx + 1);
                       break;

                    case 1:
                        dfs(num - numbers[idx], idx + 1);
                        break;

                    case 2 :
                        dfs(num * numbers[idx], idx + 1);
                        break;

                    case 3:
                        dfs(num / numbers[idx], idx + 1);
                        break;
                }
                operators[i]++;
            }
        }
    }
}