[25.03.15] 연산자 끼워넣기

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    static Map<Integer,ArrayList<Integer>> map;
    static int N;
    static int[] arr;
    static int[] op = new int[4];
    static int min=Integer.MAX_VALUE;
    static int max=Integer.MIN_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr= new int[N];
        map=new HashMap<Integer,ArrayList<Integer>>();
        for(int i=0; i<N; i++){
            map.put(i,new ArrayList<Integer>());
        }
        String[] s= br.readLine().split(" ");
        for(int i=0; i<s.length; i++){
            arr[i]= Integer.parseInt(s[i]);
        }
        s= br.readLine().split(" ");
        for(int i=0; i<s.length; i++){
            op[i]= Integer.parseInt(s[i]);
        }

        dfs(0,op,arr[0]);
        System.out.printf("%d\n%d",max,min);
        

    }
    public static void dfs(int depth,int[] op ,int num ){
        if(depth==N-1){
            max = Math.max(num,max);
            min = Math.min(num,min);
            return;
        }
        if(isVisited(depth,num)){
            return;
        }
        int[] nowOp = new int[4];
        for(int i=0; i<4; i++){
            nowOp[i]=op[i];
        }

        for(int i=0 ; i<4; i++){
            if(nowOp[i]!=0){
                nowOp[i]--;
                //덧
                if(i==0){
                    num = num+arr[depth+1];
                }
                //뺼
                else if(i==1){
                    num = num-arr[depth+1];
                }
                //곱
                else if(i==2){
                    num = num*arr[depth+1];
                }
                //나
                else{
                    if(num<0){
                        int temp = (-num)/arr[depth+1];
                        num = -temp;
                    }
                    else{
                        num = num/arr[depth+1];
                    }
                }
                map.get(depth).add(num);
                dfs(depth+1,nowOp,num);
            }
        }
        
    }

    public static boolean isVisited(int depth, int num){
        ArrayList<Integer> list;
        if(map.containsKey(depth)){
            list = map.get(depth);
        }
        else{
            return false;
        }
        for(int k :list){
            if(k==num){
                return true;
            }
        }
        return false;
            
    }
    
}​

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static int[] arr;
    // op[0] = + 개수, op[1] = - 개수, op[2] = * 개수, op[3] = / 개수
    static int[] op = new int[4];
    static int maxVal = Integer.MIN_VALUE;
    static int minVal = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // N 입력
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        // 수열 입력
        String[] tokens = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tokens[i]);
        }
        
        // 연산자 개수 입력
        tokens = br.readLine().split(" ");
        for (int i = 0; i < 4; i++) {
            op[i] = Integer.parseInt(tokens[i]);
        }
        
        // DFS 시작 (초기 depth = 1, 현재 값 = arr[0])
        dfs(1, arr[0]);
        
        // 결과 출력
        System.out.println(maxVal);
        System.out.println(minVal);
    }
    
    static void dfs(int depth, int currentVal) {
        // 모든 수(또는 연산자)를 사용한 경우
        if (depth == N) {
            maxVal = Math.max(maxVal, currentVal);
            minVal = Math.min(minVal, currentVal);
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            // 사용할 수 있는 연산자가 남아 있으면
            if (op[i] > 0) {
                op[i]--;  // 해당 연산자 하나 소모
                int nextVal = currentVal;

                switch (i) {
                    case 0: // +
                        nextVal += arr[depth];
                        break;
                    case 1: // -
                        nextVal -= arr[depth];
                        break;
                    case 2: // *
                        nextVal *= arr[depth];
                        break;
                    case 3: // /
                        if (nextVal < 0) {
                            nextVal = -(-nextVal / arr[depth]);
                        } else {
                            nextVal = nextVal / arr[depth];
                        }
                        break;
                }
                
                // 다음 단계 탐색
                dfs(depth + 1, nextVal);
                
                // 연산자 개수 복원
                op[i]++;
            }
        }
    }
}

 

SWEA 1244와 아주 닮았다고 생각했었는데 틀렸다. 왜지?

 

내가 푼 풀이가 틀린 이유:

SWEA 1244번처럼 백트래킹을 통해 가지치기를 하려고 했다. 왜냐하면 전부 완탐쳐버리면 매 뎁스마다 +-*% 의 4가지씩 나오므로 최대 11 뎁스일 경우 4의 10승이었다. 당연히 시간초과 날 것이기에 무조건 가지치기를 하자고 생각했고 이때 1244번처럼 (현재 뎁스 + 현재까지 계산된 숫자) 의 조합으로 저장하고 있다가 이 두 조합 모두 맞아떨어지면 가지치기 하겨고 했다.

그 과정에서 Map<Integer, ArrayList<Integer>> 로 억지로라도 뎁스 + 숫자의 조합 저장소를 만들려고 발악을 했다.

 

문제는 내가 연산자 횟수에 제한이 있다는 것을 간과했다.

 

2뎁스에서 어떻게 연산이 진행되었던간에 현재는 계산된 숫자가 5라면 (뎁스:2 , 숫자:5) 로 오는 모든 검색 과정은 가지치기를 하면 안되고 여기에 남아있는 연산자 횟수까지 같아야 가지치기가 된다.

 

(뎁스: 2, 숫자: 5) + (0 , 0 , 1 , 1) 과 (뎁스: 2, 숫자: 5) + (0 , 1 , 1 , 0 ) 는 엄연히 다르기 때문이다.

 

여기서 중요한 것은 가지치기를 굳이 하지 않더라도 남아있는 연산자 횟수 덕분에 가짓수가 확 줄어들어 시간초과가 나지 않음이다. 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------

라고 글쓰면서 생각했지만...

 

4의 10승은 1억도 안된다. 미쳤나보다. 4의 10승이 1억이 넘어가는줄 알아서 시간초과 걸린줄 알았다. 이렇게 쉬운 문제를...