자바(백준) 14888 연산자 끼워넣기

오답 노트 & 새로 알게 된 점

이 문제는 숫자는 가만히 놔두고, 중간에 연산자를 끼워넣어 앞에서부터 계산하는 방식이다.

 

숫자는 최대 11개이다. 그렇다면 연산은 최대 10개이다.

 

여기서 시간복잡도를 생각해보면,

자리 10개 중에 사칙연산 중에 하나를 선택해야한다. 그리고 중복을 포함하지 않는다.

그렇다면 아마 시간 복잡도는 10P4라고 생각이 든다.(나의 예상)

 

그리고 문제에서 계산 중간이나 결과값은 int범위라고 나와있다.

 

보편화된 백트레킹 풀이인 것 같다.

단지 visit배열이 아닌 op배열을 이용하여 연산자의 개수를 1개씩 없애면서 진행하면 된다.

 

 

---

코드

 

package BackTracking;
 
import java.io.*;
import java.util.StringTokenizer;
 
public class BOJ14888 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static int op[] = new int[5];
    static int A[];
    static int orders[];
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
 
        StringTokenizer st;
 
        A = new int[N + 1];
        orders = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i < 5; i++) {
            op[i] = atoi(st.nextToken());
        }
 
        pro(1, A[1]);
 
        sb.append(max + "\n" + min);
 
        System.out.print(sb);
    }
 
    private static void pro(int cnt, int value) {
        if (cnt == N) {
            max = Math.max(value, max);
            min = Math.min(value, min);
            return;
        }
 
        for (int i = 1; i <= 4; i++) {
            if(op[i] > 0){
                op[i]--;
                int newValue = value;
                if(i == 1){
                    newValue += A[cnt + 1];
                }
                if(i == 2){
                    newValue -= A[cnt + 1];
                }
                if(i == 3){
                    newValue *= A[cnt + 1];
                }
                if(i == 4){
                    newValue /= A[cnt + 1];
                }
                pro(cnt + 1, newValue);
                op[i]++;
            }
        }
    }
}