14888번

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

14888번: 연산자 끼워넣기

나는 맨처음에 조금 접근을 잘못했다.

나는 계산부호를 어떻게 접근해야할지 모르겠어서 고민하다가 HashMap도 생각해 보았다. 하지만 HashMap은 접근하기 좀 까다로운 것 같았다. 그래서 내가 맨처음 생각한 접근방식인 숫자 배열은 무시하고 계산부호를 dfs를 통해 나열하고, 그 다음 부호의 깊이가 n-1이 되면 배열과 연결하여 계산하고 최대최소값을 바꾸는 방식을 구현하기에는 어려움이 있었다.

그래서 다른 방법은 무엇이 있을까 고민하다가 결국 질문게시판을 봐버렸다...

 

그중에서는 내가 생각했던 방식을 변형하여서 깊이마다 부호를 바꾸는 형식으로 구현한 사람의 것을 보았다.

그걸보고 바로 떠올라서 구현했다. (물론 그 사람걸 참고했다...ㅎㅎ)

 

그래서 이전에 N과M 중에 주어진 배열을 사용하는 방식과 유사하게 만들었다.

먼저 부호의 갯수가 들어 있는 배열을 이용해서 값이 0이 아니면 그 부호에 대해 식을 계산하는 것이다.

중요한건 부호는 4개 뿐이어서 경우는 0,1,2,3이다.

0은+, 1은-, 2는*, 3은/ 이다.

그렇게 식을 써서 아래와 같이 구현했다. 여기서 부호의 값을 빼주고 나중에 더해주는 이유는 백트레킹 과정에서 다시 사용할 수 있게 만들기 위해서다.

package backjoon;

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

public class b14888 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int[] sign = new int[4];
        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++){
            sign[i]= Integer.parseInt(st.nextToken());
        }

        T t1 = new T(N,sign,arr);
        t1.dfs(arr[0],1);
        System.out.println(t1.max+" "+t1.min);
    }
}
class T {
    int n;
    int[] arr;
    int[] sign;
    String[] answer;
    int min=Integer.MAX_VALUE;
    int max=Integer.MIN_VALUE;
    public T(int n, int[] sign, int[] arr){
        this.n = n;
        this.sign = sign;
        this.arr=arr;
        answer = new String[n];
    }
    public void dfs(int num,int depth){
        if(depth==n){
            min = Math.min(min,num);
            max = Math.max(max,num);
            return;
        }
        for(int i=0; i<4; i++){
            if(sign[i]>0){
                sign[i]--;//사용한 부호의 갯수를 감소 시킨다.
                if(i==0){
                    dfs(num+arr[depth],depth+1);
                } else if (i==1) {
                    dfs(num-arr[depth],depth+1);
                } else if (i==2) {
                    dfs(num*arr[depth],depth+1);
                } else if (i==3) {
                    if(num<0){
                        int tmp = -Math.abs(num)/arr[depth];
                        dfs(tmp,depth+1);
                    }
                    else {
                        dfs(num/arr[depth],depth+1);
                    }
                }//나누는 값이 음수인 경우와 양수인 경우로 나누어 생각한다.
                sign[i]++;//사용한 부호를 다시 돌려놓아 다른 부호나열에 사용할 수 있게한다.
            }
        }
    }
}