[Baekjoon] 백준 알고리즘: 14888 - 연산자 끼어넣기

문제

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

 

첫번째 나의 풀이

import java.util.Scanner;
 
public class Main {
 
    static int min = Integer.MAX_VALUE;
 
    static int max = Integer.MIN_VALUE;
 
    static int calsNum;
    
    static int[] cals;
 
    static int[] num;
 
    public static void main(String[] args) {
        Main T = new Main();
 
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        sc.nextLine();
        calsNum = n - 1;
 
        num = new int[n]; // 숫자
        String s1 = sc.nextLine();
        String[] string1 = s1.split(" ");
 
        for(int i = 0; i < string1.length; i++){
            num[i] = Integer.parseInt(string1[i]);
        }
 
        String s2 = sc.nextLine();
        String[] strings2 = s2.split(" ");
        cals = new int[4]; // 연산자
        for(int i = 0; i < 4; i++){
            cals[i] = Integer.parseInt(strings2[i]);
        }
 
        T.solution();
        System.out.println(max);
        System.out.println(min);
    }
 
    private void solution() {
        dfs(0, num[0]);
    }
 
    private void dfs(int depth, int sum) {
        // 연산자 갯수 모두 사용했다면
        if(depth == calsNum){
            max = Math.max(max, sum);
            min = Math.min(min, sum);
 
            return;
        }
        
        // 연산자
        for(int i = 0; i < 4; i++){
            if(cals[i] == 0){
                continue;
            }
 
            cals[i] -= 1;
 
            // 사칙연산 결과를 별도로 계산
            int nextSum = 0;
            if(i == 0){
                nextSum = sum + num[depth + 1];
            } else if (i == 1) {
                nextSum = sum - num[depth + 1];
            } else if (i == 2) {
                nextSum = sum * num[depth + 1];
            } else if (i == 3) {
                nextSum = sum / num[depth + 1];
            }
 
            dfs(depth + 1, nextSum);
            cals[i] += 1;
        }
    }
}

내가 생각했던 풀이과정

대표 알고리즘: 백트래킹

1. 숫자와 연산자를 각각의 배열로 저장한다.
2. 연산자는 입력받은 숫자의 - 1개가 필요하기 때문에 연산자 갯수를 calsNum 에 저장해뒀다
3. 만약 dfs의 깊이가 필요 연산자 갯수랑 같다면 더이상 연산할 필요가 없기 때문에 얼리 리턴을 해주며 dfs 호출을 반환한다
4. 만약 더 연산이 필요하다면 연산자의 반복문 갯수 4개만큼 반복문을 돈다
5. 반복문을 돌면서 사용할 수 있는 연산자가 0이라면 반복문을 탈출하고, 그렇지 않다면 사용한 반복문의 연산자 갯수를 -1 감소시킨다
6. 기존 재귀함수의 sum결과를 기억해야하기 때문에 sum을 덮어쓰지 않고, 새로운 변수 nextSum에 결과 저장한다.
   1. sum 값을 변경하면 다른 재귀 호출에 영향을 미치기 때문에, 연산 결과를 nextSum에 저장하여 안전하게 처리합니다.
7. dfs호출이 끝났다면 다른 재귀를 위해 사용한 연산자를 되돌려준다(백트래킹)

결과: O

 

다른 사람의 풀이

.

 

새로 알게된 점, 확인해야할 점