[코딩 테스트] 연산자 끼워넣기

문제 출처

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

 

문제풀이 생각과 과정

• 백트래킹을 통해서 연산자가 없는 경우는 pruning해줘야겠다고 생각을 하였음
• 모든 연산자 순서를 구한다음 max랑 min을 구해도 숫자가 11개 이하이기에 문제 없을거라고 생각하였음

 

다음과 같이 간단하게 생각하고, 그래프를 그려보았다.

예시의

예제 입력 3 복사

6
1 2 3 4 5 6
2 1 1 1

 

이 부분을 보고 숫자라 6개인 경우에 대해서 그래프를 그려보았다.

 

다음과 같이 각 연산자의 갯수에 따라 그래프의 갯수가 늘어나게 된다.

 

최종 그래프 모양은 아래와 같을 것이다.

 

모든 경우를 저렇게 숫자의 갯수만큼의 깊이로 내려간다음에 Max랑 Min을 업데이트해주고 최종 결과를 return을 해준다.

 

코드

• 문제의 조건에서 최대값과 최소값은 10억,-10억을 넘지 않는다고 해서 max랑 min을 각각 -10억,10억으로 초기화 해주었음

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

public class Main {
    private static int N;
    private static int[] numbers;

    private static int[] operator;

    private static int max;
    private static int min;


    public static void main(String[] args)throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        numbers = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        // 세 번째 입력: 연산자 개수 (+, -, *, / 순)
        operator = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        max = -1000000000;
        min = 1000000000;

        findSolution(1,numbers[0]);





        System.out.println(max);
        System.out.println(min);
    }

    private static void findSolution(int index,int result){
        if(index==N){
            max = Math.max(result,max);
            min = Math.min(result,min);
            return;
        }
        for(int i=0;i<4;i++){
            if(operator[i]==0) continue;
            operator[i]--;
            findSolution(index+1,operate(result,numbers[index],i));
            operator[i]++;
        }
    }

    private static int operate(int o1, int o2, int op){
        if(op==0) return o1+o2;
        else if(op==1) return o1-o2;
        else if(op==2) return o1*o2;
        else return o1/o2;
    }
}