[BOJ] 14888. 연산자 끼워넣기(순열)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

문제에서 

"주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다."

라고 했는데, 그렇다면 5!로, 5x4x3x2x1 = 120 가지가 나와야 하는데 왜 60가지지..? 라는 의문을 가졌었다.

혹시나 하고 질문 리스트를 확인해본 결과

"덧셈 2개는 구분할 수 없으므로 2로 나눠줘야 합니다." 

라는 글이 있었다...

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer;   public class BOJ14888 {       // 덧셈, 뺄셈, 곱셈, 나눗셈     static int[] operation, nums, visit;     static int N, resMax, resMin;          public static void main(String[] args) throws NumberFormatException, IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                  N = Integer.parseInt(br.readLine());         nums = new int[N];         visit = new int[4];         operation = new int[4];         // An 입력         StringTokenizer st = new StringTokenizer(br.readLine(), " ");         for (int i = 0; i < N; i++)              nums[i] = Integer.parseInt(st.nextToken());         // 연산자 개수 입력         StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");         for (int i = 0; i < 4; i++)              operation[i] = Integer.parseInt(st2.nextToken());                  resMax = -987654321;         resMin = 987654321;         // 주어진 수의 순서를 바꾸면 안돼         // 연산자 우선순위를 무시하고 앞에서 부터 진행         process(1, nums[0]);                  // 최대인 것과 최소인 것         bw.write(resMax + "\n" + resMin);         bw.flush();                  br.close();         bw.close();     }       public static void process(int idx, int sum) {         // 주어진 수의 연산을 완료했을 때,         if(idx == N) {             resMax = Math.max(resMax, sum);             resMin = Math.min(resMin, sum);             return;         }                  for (int i = 0; i < 4; i++) {             // 입력받은 연산자가 있고, 사용되지 않은 연산자를 사용해보자             if(operation[i] != 0 && visit[i] != operation[i]) {                 // 이 연산자를 지금 사용할래!                 visit[i]++;                 // 0:덧셈, 1:뺄셈, 2:곱셈, 3:나눗셈                 // 연산자를 사용하지 않을 경우 sum 연산자를 그대로 넘겨줘야하기 때문에 tmp 변수 사용                 int sumTmp = sum;                 if(i==0) sumTmp += nums[idx];                 else if(i==1) sumTmp -= nums[idx];                 else if(i==2) sumTmp *= nums[idx];                 else {                     // 나눗셈은 정수 나눗셈으로 몫만                     if(sumTmp >= 0) sumTmp /= nums[idx];                     else {                         // 음수를 양수로 나눌 때는 음수를 양수로 바꾼 뒤 몫을 취하고 음수로 바꿔                         sumTmp *= -1;                         sumTmp /= nums[idx];                         sumTmp *= -1;                     }                                      }                         process(idx + 1, sumTmp);                 // 이 연산자를 지금 사용 안함                 visit[i]--;             }         }     }      }   Colored by Color Scripter

cs

음 그나마 짚고 넘어가야 할 부분이라면

line 56.에서 사용할 수 있는 연산자가 없다면 넘겨주는 것? 

line 78.에서 연산자를 사용하지 않을 경우, sum이 변화하면 안되지만 위에 line56~75.에서 sum값이 변한다.

그래서 original sum을 보존(?)하기 위해 sumTmp 변수를 사용하였다.