[백준/JAVA] 14888번: 연산자 끼워넣기

🔺 문제

14888번: 연산자 끼워넣기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static int MAX = Integer.MIN_VALUE;  // 최댓값
    public static int MIN = Integer.MAX_VALUE;  // 최솟값
    public static int[] sign = new int[4];      // 부호
    public static int[] num;                    // 숫자
    public static int N;                        // 숫자 개수
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 수 개수 받기
        N = Integer.parseInt(br.readLine());
        num = new int[N];
        
        // 숫자 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < N ; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        
        // 연산자 받기
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < 4 ; i++) {
            sign[i] = Integer.parseInt(st.nextToken());
        }
        
        // 브루트포스 & 백트래킹
        DFS(num[0], 1);
        
        System.out.println(MAX);
        System.out.println(MIN);
    }
    
    public static void DFS(int n, int idx) {
        // 모든 연산자를 썼을 경우
        if(idx == N) {
            MAX = Math.max(MAX, n);
            MIN = Math.min(MIN, n);
            return;
        }
        
        for(int i = 0 ; i < 4 ; i++) {
            // 연산자 개수가 1개 이상인 경우
            if(sign[i] > 0) {
                sign[i]--;    // 해당 연산자 1 감소
                
                switch(i) {
                    case 0: DFS(n + num[idx], idx + 1); break;
                    case 1: DFS(n - num[idx], idx + 1); break;
                    case 2: DFS(n * num[idx], idx + 1); break;
                    case 3: DFS(n / num[idx], idx + 1); break;
                }
                
                sign[i]++;  // 재귀 호출 종료 시, 해당 연산자 개수 복구 (다른 경우의 수 탐색 위해 / 백트래킹)
            }
        }
    }
}

✅ 해결 아이디어
✔ 브루트포스 & 백트래킹
- 연산 기호가 0이 될 때까지 재귀 돌려주기
- 연산하기 전 1 감소시키고, 연산 후 다시 돌려주기 (다른 경우의 수 탐색 위해 / 백트래킹)

 

---

💬 느낀 점

으앙 모르겠어서 다른 분 코드 보고 제출했다...

복습을 많이 해야겄다..

 

완전탐색.. 재귀.. 백트래킹.. DFS..

 

 

1회독	2회독	3회독	4회독	5회독
V	9.16

---

(참고)

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

[백준 알고리즘] 백준 14888번 연산자 끼워넣기 자바(Java)