[swea/4008] 숫자 만들기 - Java 자바

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH

SW Expert Academy

 

개념: 완전탐색, dfs

 

문제 설명

선표는 게임을 통해 사칙 연산을 공부하고 있다.

N개의 숫자가 적혀 있는 게임 판이 있고, +, -, x, / 의 연산자 카드를 숫자 사이에 끼워 넣어 다양한 결과 값을 구해보기로 했다.

수식을 계산할 때 연산자의 우선 순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.

예를 들어 1, 2, 3 이 적힌 게임 판에 +와 x를 넣어 1 + 2 * 3을 만들면 1 + 2를 먼저 계산하고 그 뒤에 * 를 계산한다.

즉 1+2*3의 결과는 9이다.

 

주어진 연산자 카드를 사용하여 수식을 계산했을 때 그 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고, 두 값의 차이를 출력하시오.

---

 

풀이

연산자 개수를 int[] operator에 입력 받고, 숫자는 int[] number에 입력 받는다.

완전탐색을 통해 구한다. dfs로 구현한다.

 

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static int[] number, operator;
    static int N, minVal, maxVal;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());
        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            number = new int[N];
            operator = new int[4];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 4; i++) {
                operator[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                number[i] = Integer.parseInt(st.nextToken());
            }

            minVal = Integer.MAX_VALUE;
            maxVal = Integer.MIN_VALUE;

            dfs(1, number[0]); // 이미 첫번째 숫자는 처리했으니까 depth = 1

            System.out.println("#" + t + " " + (maxVal - minVal));
        }
    }

    public static void dfs(int depth, int sum) {
        if (depth == N) {
            minVal = Math.min(minVal, sum);
            maxVal = Math.max(maxVal, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (operator[i] == 0) {
                continue;
            }
            operator[i]--;
            if (i == 0) {
                dfs(depth + 1, sum + number[depth]);
            } else if (i == 1) {
                dfs(depth + 1, sum - number[depth]);
            } else if (i == 2) {
                dfs(depth + 1, sum * number[depth]);
            } else {
                dfs(depth + 1, sum / number[depth]);
            }
            operator[i]++;
        }
    }
}