문제 링크

접근 방식

• 숫자 조합 + 연산자 조합을 일단 만들어서
• 그걸 계산한 후에
• Math.max, Math.min으로 계산하기
  이렇게 3단계로 나눠야겠다고 생각했다.

헷갈렸던 부분

1. 숫자 조합과 연산자 조합 따로인줄

그래서 dfs 메소드를 두개로 나눠서 이걸 어떻게 조합하지..? StringBuilder? 이러고 헤맸는데 알고보니 dfs 안에서 백트래킹을 이용하면 다 해결가능했던 것..

• 숫자 조합은 매번 계산해서 결과 값을 넘겨주면 되고
• 연산자는 아래처럼 재귀를 사용하면 모든 경우 조합 가능하다

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

                int next = calculate(currentValue, arr[depth], i);

                dfs(depth + 1, next);
                operator[i]++; // 백트래킹
            }
        }

2. 넘겨주는 값 확인 잘하기

• dfs(1, arr[0])
  • 위 부분을 dfs(0, 0)으로 잘못 넣고 있어서 매우 이상한 값이 답으로 나옴
  • 애초에 처음부터 arr[0]을 결과값으로 넣으면 되기 때문에 arr[0]을 currentValue로 넣고
  • depth도 1부터 시작해야 N까지 탐색 가능하다.
    • 0부터 N-1이면 N번 탐색은 가능하지만 arr[N-1] 탐색이 안되기 때문에 안됨!
    • 아래 calculate 메소드 넘겨줄 때 arr[depth] 넘겨주니까~ 주의
• calculate(int sum, int num, int op)
  • 여기도 처음에 op이 아니라 operator[i]를 넘기고 있었다... 걍 생각없이 매개변수 넘기는 듯.. 주의하기

3. 나눗셈 간단하게 구현하기

        if (op == 3) {
          if (sum < 0 && num < 0) {
              sum *= -1;
              num *= -1;
              sum /= num;
          }
          else if (sum < 0) {
              sum *= -1;
              sum /= num;
              sum *= -1;
          }
          else if (num < 0) {
              num *= -1;
              sum /= num;
              sum *= -1;
          }
          else {
              sum /= num;
          }

• 음수일 경우를 판단하느라 노.가.다로 풀었는데 알고보니 아래 코드면 해결된다고 한다..
• 지금 보니 위 코드에서 num < 0은 왜 확인한거지;;

          if (op == 3) {
            if (sum < 0) return - ( Math.abs(sum) / num );
            else return sum / num;
        }

정답 코드

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

public class BOJ_14888_연산자끼워넣기_S1 {
    static int N;
    static int[] arr;
    static int[] operator = new int[4]; // +, -, x, ÷
    static int maxAnswer = Integer.MIN_VALUE;
    static int minAnswer = Integer.MAX_VALUE;

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

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++)
            operator[i] = Integer.parseInt(st.nextToken());

        // 숫자조합
        // 연산자조합
        //index: arr에서 현재 몇 번째 숫자를 사용할지
        //currentValue: 앞까지 계산된 결과
        dfs(1, arr[0]);
        // 그 조합끼리 계산

        System.out.println(maxAnswer);
        System.out.println(minAnswer);

    }

    public static void dfs(int depth, int currentValue) {
        if (depth == N) {
            maxAnswer = Math.max(currentValue, maxAnswer);
            minAnswer = Math.min(currentValue, minAnswer);
            return;
        }

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

                int next = calculate(currentValue, arr[depth], i);

                dfs(depth + 1, next);
                operator[i]++; // 백트래킹
            }
        }

    }

    public static int calculate(int sum, int num, int op) {
        if (op == 0)
            sum += num;
        if (op == 1)
            sum -= num;
        if (op == 2)
            sum *= num;
        if (op == 3) {
            if (sum < 0) return - ( Math.abs(sum) / num );
            else return sum / num;
        }

        return sum;
    }
}