BOJ) 연산자 끼워넣기

연산자 끼워넣기

14888번: 연산자 끼워넣기

풀이

 

어렵지 않은 문제지만, 푸는데 많은 시간이 들었다.

return하는 부분에서 조건을 잘못 설정해줘서 찾는데 한참이 걸렸다.. ㅎㅎ ㅠㅠ

 

방법은 간단하다.

숫자 배열을 입력받아 저장하고, 연산자 배열(+,-,*,/ 순서)을 저장하면 이 문제는 끝이다.

숫자 사이사이 연산자를 집어 넣는 경우로, 숫자 배열을 가리키는 index를 통해 DFS를 풀어나가면 된다.

 

여기서 숫자 배열을 가리키는 Index를 연산 오른쪽에 오는 숫자로 정했다.

index가 숫자 배열의 크기를 벗어나면 dfs는 종료된다.

이 때, max값과 min값을 최신화 해줬다.

 

저장되어있는 연산자 갯수 배열을 돌면서, 0보다 큰 경우에 하나씩 줄여주면서

지금까지 저장해 온 숫자와 연산 오른쪽에 들어가는 숫자를 넣고, 연산자의 종류에 따라 +-*/ 해주었다.

 

왜 오래걸렸는지는 잘 모르겠지만, 어려운 문제는 아니었다고 생각한다..

 

 

코드

 

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

public class Operator_14888 {
    final static int operatorSize = 4;
    static int n, numArr[];
    static long min, max;

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

        numArr = new int[n];
        int[] operators = new int[operatorSize];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0; i<n; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());

        for(int i=0; i<operatorSize; i++) {
            operators[i] = Integer.parseInt(st.nextToken());
        }

        solution(operators);

        br.close();
    }

    private static void solution(int[] operators) {
        min = 1000000000;
        max = -1000000000;

        dfs(1, numArr[0], operators);
        System.out.println(max);
        System.out.println(min);
    }

    private static void dfs(int next, int sum, int[] operators) {
        if(next == n) {
            max = Math.max(max,sum);
            min = Math.min(min,sum);
            return;
        }

        for(int i=0; i<operatorSize; i++) {
            if(operators[i] >0) {
                operators[i]--;
                dfs(next+1,getNum(i,sum,numArr[next]), operators);
                operators[i]++;
            }
        }
    }

    private static int getNum(int cmd, int left, int right) {
        int result =0;
        switch (cmd) {
            case 0:
                result = left+right;
                break;
            case 1:
                result = left-right;
                break;
            case 2:
                result = left*right;
                break;
            case 3:
                result = left/right;
                break;
            default:
                break;
        }
        return result;
    }
}