🥈 [Baekjoon / Java] 14888. 연산자 끼워넣기

이하얀·2024년 5월 16일

14888 Java baekjoon 백엔드 백준 알고리즘 연산자 끼워넣기 자바

🐣 백준

목록 보기

13/37

문제 설명

💡 Info

난이도 : 실버 1
시간 제한 : 2초
메모리 제한 : 512MB
백준 링크: https://www.acmicpc.net/problem/14888
풀이 링크(GitHub): hayannn/CodingTest_Java/백준/Silver/14888. 연산자 끼워넣기

내용

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

📥입력 조건

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

📤출력 조건

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

입출력 예시

입력 1
```
2
5 6
0 0 1 0
```
출력 1
```
30
30
```

입력 2
```
3
3 4 5
1 0 1 0
```
출력 2
```
35
17
```

입력 3
```
6
1 2 3 4 5 6
2 1 1 1
```
출력 3
```
54
-24
```

유의 사항 및 제약 조건

Hint
- 세 번째 예제의 경우에 다음과 같은 식이 최댓값/최솟값이 나온다.
  - 최댓값: 1-2÷3+4+5×6
  - 최솟값: 1+2+3÷4-5×6

문제 이해

N개의 수와 N-1개의 연산자가 주어지면, 만들 수 있는 식의 결과 중 최대와 최소를 출력하기
- 단, 연산자 우선 순위 무시하고 앞에서부터 진행!
- 나눗셈은 정수 나눗셈으로 몫만 취함!

알고리즘

실제 풀이 시간 : 30분

입력
- 수의 개수 N 입력받기
- 수열 입력받기(배열)
- 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수 입력받기
계산
- 최대 : 나눗셈, 덧셈, 뺄셈, 곱셈 순으로 끼워넣기
  - 단, 개수를 모두 소비할 때까지 같은 연산자가 연속으로 들어가도록 작성
- 최소 : 덧셈, 뺄셈, 곱셈, 나눗셈 순으로 끼워넣기
  - 단, 개수를 모두 소비할 때까지 같은 연산자가 연속으로 들어가도록 작성

import java.util.*;
public class BJ14888 {

    static int N;
    static int[] num;
    static int[] oper;
    static int maxResult = Integer.MAX_VALUE;
    static int minResult = Integer.MIN_VALUE;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        int[] num = new int[N];
        for(int i=0; i<N; i++){
            num[i] = sc.nextInt();
        }

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

        int result = 0;

        for(int i=0; i<4; i++){
            int index = 0;
            if(oper[i] > 0) {
                switch (i) {
                    case 0:
                        Math.max(num[index] / num[index], index / 1);
                        break;
                    case 1:
                        Math.max(num[index] + num[index], index - 1);
                        break;
                    case 2:
                        Math.max(num[index] - num[index], index - 1);
                        break;
                    case 3:
                        Math.max(num[index] * num[index], index * 1);
                        break;
                }
                maxResult = Math.max(maxResult, result);
                minResult = Math.min(minResult, result);
            }
        }
        System.out.println(maxResult);
        System.out.println(minResult);
    }
}

오답 체크

DFS를 사용하지 않고, 바로 계산해 int형의 최댓값과 최솟값이 입력과 관계없이 나오는 문제 발생

DFS 선언하고 조건을 추가해 해결

//before
int result = 0;

        for(int i=0; i<4; i++){
            int index = 0;
            if(oper[i] > 0) {
                switch (i) {
                    case 0:
                        Math.max(num[index] / num[index], index / 1);
                        break;
                    case 1:
                        Math.max(num[index] + num[index], index - 1);
                        break;
                    case 2:
                        Math.max(num[index] - num[index], index - 1);
                        break;
                    case 3:
                        Math.max(num[index] * num[index], index * 1);
                        break;
                }
                maxResult = Math.max(maxResult, result);
                minResult = Math.min(minResult, result);
            }
        }
        System.out.println(maxResult);
        System.out.println(minResult);

값이 출력이 되기는 하지만, 여전히 잘못된 값이 출력되는 문제 발생

Switch-case문의 연산자 계산 케이스를 순서를 일반적인 +, -, /, * 순으로 다시 재구성

연산 다음에는 다음 숫자로 넘어가도록 구성해서 해결

//ing
...
    static int maxResult = Integer.MIN_VALUE; // 초기 최대값을 가장 작은 값으로 설정
    static int minResult = Integer.MAX_VALUE; // 초기 최소값을 가장 큰 값으로 설정
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        ...

        dfs(num[0], 1); // 초기 값은 수열의 첫 번째 숫자부터 시작

        System.out.println(maxResult);
        System.out.println(minResult);
    }
		...

                switch (i) {
                    case 0:
                        //dfs 뒷부분 변수를 모두 다음 수를 의미하는 index+1로 변경하기!
                        dfs(num[index] / num[index], index + 1);
                        break;
                    case 1:
                        dfs(num[index] + num[index], index + 1);
                        break;
                    case 2:
                        dfs(num[index] - num[index], index + 1);
                        break;
                    case 3:
                        dfs(num[index] * num[index], index + 1);
                        break;
                }
                //재귀호출 종료 후 연산자 개수 복구하기
                oper[i]++;
            }
        }
    }
}

//after
for (int i = 0; i < 4; i++) {
  if (oper[i] > 0) {
      oper[i]--;

      int nextNum = 0;
      switch (i) {
          case 0:
              nextNum = oneNum + num[index];
              break;
          case 1:
              nextNum = oneNum - num[index];
              break;
          case 2:
              nextNum = oneNum * num[index];
              break;
          case 3:
              nextNum = oneNum / num[index];
              break;
      }

      dfs(nextNum, index + 1);
      oper[i]++; // 재귀 호출이 끝난 후 연산자 개수 복구
  }
}
}

최종 풀이

코드 참고
[백준] 14888번 : 연산자 끼워넣기 - JAVA [자바]

실제 풀이 시간 : 51분(첫 풀이 포함)

입력
- 수의 개수 N 입력받기
- 수열 입력받기(배열)
- 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수 입력받기
계산
- 최대와 최소 변수 선언 후 DFS로 재귀 호출하기
- index == N 즉, 모든 숫자를 다 사용한 경우 Math.max와 Math.min이 나오는 조건 구성
- 그 다음, 들어온 숫자를 switch-case문으로 +,-,/,* 연산 진행

import java.util.*;
public class Main {

    static int N;
    static int[] num;
    static int[] oper;
    static int maxResult = Integer.MIN_VALUE; // 초기 최대값을 가장 작은 값으로 설정
    static int minResult = Integer.MAX_VALUE; // 초기 최소값을 가장 큰 값으로 설정
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        num = new int[N];
        for(int i=0; i<N; i++){
            num[i] = sc.nextInt();
        }

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

        dfs(num[0], 1); // 초기 값은 수열의 첫 번째 숫자부터 시작

        System.out.println(maxResult);
        System.out.println(minResult);
    }

    public static void dfs(int oneNum, int index){
        if(index == N) { // 모든 숫자를 다 사용한 경우
            maxResult = Math.max(maxResult, oneNum);
            minResult = Math.min(minResult, oneNum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (oper[i] > 0) {
                oper[i]--;

                int nextNum = 0;
                switch (i) {
                    case 0:
                        nextNum = oneNum + num[index];
                        break;
                    case 1:
                        nextNum = oneNum - num[index];
                        break;
                    case 2:
                        nextNum = oneNum * num[index];
                        break;
                    case 3:
                        nextNum = oneNum / num[index];
                        break;
                }

                dfs(nextNum, index + 1);
                oper[i]++; // 재귀 호출이 끝난 후 연산자 개수 복구
            }
        }
    }
}

이하얀

언젠가 내 코드로 세상에 기여할 수 있도록, BE&Data Science 개발 기록 노트☘️