[백준 15658] 연산자 끼워넣기 (2) [Java]

문제

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

 

---

풀이

배열 A에 대해 주어진 연산자를 활용해 만들어지는 모든 식의 결과 중 최대/최소값을 구하는 문제다.

중간값과, 다음에 계산할 요소의 인덱스를 넘겨주는 방식으로 풀이했다.

만약 인덱스가 A의 길이와 같다면 더 이상 연산할 요소가 없기 때문에 연산을 중단하고 결과를 갱신했다.

    private static void bt(int temp, int nextIdx) {
        if (nextIdx == A.length) {
            max = Math.max(max, temp);
            min = Math.min(min, temp);
            return;
        }

아직 연산할 요소가 남아있는 경우에는 연산자 배열 OP에 대해 남아있는 연산자들의 수 만큼 연산 후 중간 값을 넘겨주었다.

        for (int i = 0; i < 4; ++i) {
            if (OP[i] > 0) {
                --OP[i];
                switch (i) {
                    case 0:
                        bt(temp + A[nextIdx], nextIdx + 1);
                        break;
                    case 1:
                        bt(temp - A[nextIdx], nextIdx + 1);
                        break;
                    case 2:
                        bt(temp * A[nextIdx], nextIdx + 1);
                        break;
                    case 3:
                        bt(temp / A[nextIdx], nextIdx + 1);
                        break;
                }
                ++OP[i];
            }
        }
    }

풀이시간

≤ 13m

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/15658.java