[백준] 14888 연산자 끼워넣기

문제보기

1. 재귀로 풀기

import java.util.*;

public class Main {
  public static int max = 9999;
  public static int min = 9999;


  // N 은 최대 11이므로 4^10 해봤자 한 백만정도밖에 안된다! 재귀 gogo  
  public static void go(int[] arr, int idx,int cur,int plus,int minus,int mul,int div){
    // 연산자가 모자란 경우는 종료
    if(plus < 0 || minus < 0 || mul < 0 || div < 0){
      return;
    }

    // 종료 조건
    if(idx == arr.length -1){
      if(max == 9999){
        max = cur;
      }
      if(min == 9999){
        min = cur;
      }
      if(max < cur){
        max = cur;
      }
      if(min > cur){
        min = cur;
      }
      return;
    }

    // 각각 +, -, *, / 일때로 나누어 다시 호출한다
    go(arr, idx+1, cur + arr[idx+1], plus-1, minus, mul, div);
    go(arr, idx+1, cur - arr[idx+1], plus, minus-1, mul, div);
    go(arr, idx+1, cur * arr[idx+1], plus, minus, mul-1, div);
    go(arr, idx+1, cur / arr[idx+1], plus, minus, mul, div-1);

  }

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    int[] oper = new int[4];


    for(int i = 0 ; i < n ; i++){
      arr[i] = sc.nextInt();
    }
    for(int i = 0 ; i < 4 ; i++){
      oper[i] = sc.nextInt();
    }

    go(arr, 0, arr[0], oper[0], oper[1], oper[2], oper[3]);
    System.out.println(max);
    System.out.println(min);

  }
}

1. 순열로 풀기

import java.util.*;

public class Main {

  // 다음 순열을 구하는 메서드
  public static boolean next_perm(int[] arr){
    int i = arr.length -1; 
    while( i > 0 && arr[i-1] >= arr[i]){
      i--;
    }
    if(i <= 0){
      return false; 
    }
    int j = arr.length -1; 
    while( arr[j] <= arr[i-1] ){
      j--;
    }

    int temp = arr[j];
    arr[j] = arr[i-1];
    arr[i-1] = temp;

    int k = arr.length -1;
    while( i < k ){
      temp = arr[k];
      arr[k] = arr[i];
      arr[i] = temp;
      i++;
      k--;
    }
    return true; 
  }

  public static int calc(int[] arr, int[] operArr){

    int ans = arr[0];

    for(int i = 0 ; i < operArr.length ; i++){
      if(operArr[i] == 0){
        ans += arr[i+1];
      }else if(operArr[i] == 1){
        ans -= arr[i+1];
      }else if(operArr[i] == 2){
        ans *= arr[i+1];
      }else{
        ans /= arr[i+1];
      }
    } 
    return ans;
  }

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    int[] operCnt = new int[4];
    int[] operArr = new int[n-1];

    for(int i = 0 ; i < n ; i++){
      arr[i] = sc.nextInt();
    }
    for(int i = 0 ; i < 4 ; i++){
      operCnt[i] = sc.nextInt();
    }
		
    // 아래는 뭔짓 한거냐면... + : 0, - : 1, .. .이렇게 해서 연산자들의 순열을 만드는것임 
    // 예를 들어 + : 2개, - : 3개, * : 4개, / : 1개 라면 
    // operArr[i] = {0, 0, 1, 1, 1, 2, 2, 2, 2, 3};
    // 과 같이 만들어진다. 이제 이걸 다음순열 함수를 이용해 모든 경우를 만들것이다
    for(int i = 0 ; i < operCnt[0] ; i++){
      operArr[i] = 0;
    }
    for(int i = operCnt[0] ; i < operCnt[0]+operCnt[1] ; i++){
      operArr[i] = 1;
    }
    for(int i = operCnt[0]+operCnt[1] ; i < operCnt[0]+operCnt[1]+operCnt[2] ; i++){
      operArr[i] = 2;
    }
    for(int i = operCnt[0]+operCnt[1]+operCnt[2] ; i < n-1 ; i++){
      operArr[i] = 3;
    }

    // 초기값 넣어주긔
    int max = calc(arr, operArr);
    int min = calc(arr,operArr);

    // 모든 연산자 순열을 넣어가면서 최대/ 최소를 뽑는다
    while(next_perm(operArr)){
      int temp = calc(arr, operArr);
      if(temp > max){
        max = temp;
      }else if(temp < min){
        min = temp;
      }
    }
    System.out.println(max);
    System.out.println(min);

  }
}

메모리는 재귀가 조금 더 잡아먹는 대신 속도는 더 빨랐음