[SWEA] 4008. 숫자 만들기

문제 링크

[SWEA] 4008. 숫자 만들기

풀이 과정

처음에는 연산자의 개수를 토대로 순열을 만들어 계산을 했지만, 시간 초과가 났습니다. 이에 재귀 함수를 호출해 순열이 다 만들어 지면 계산을 하는 방법이 아닌, 만들면서 계산까지 하는 방식으로 문제를 풀었습니다.

코드

import java.util.Scanner;

public class Solution {
    static int N;
    static int[] operator;
    static int[] operand;
    static int max;
    static int min;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TC = sc.nextInt();

        for (int tc = 1; tc <= TC; tc++) {
            max = Integer.MIN_VALUE;
            min = Integer.MAX_VALUE;

            N = sc.nextInt();

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

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

            solve(1, operand[0]);

            System.out.println("#" + tc + " " + (max - min));
        }
    }

    private static void solve(int depth, int sum) {
        if (depth == N) {
            max = Math.max(max, sum);
            min = Math.min(min, sum);

            return;
        }

        for (int i = 0; i < 4; i++) {
            if (operator[i] == 0)
                continue;

            operator[i]--;

            switch (i) {
                case 0:
                    solve(depth + 1, sum + operand[depth]);
                    break;
                case 1:
                    solve(depth + 1, sum - operand[depth]);
                    break;
                case 2:
                    solve(depth + 1, sum * operand[depth]);
                    break;
                case 3:
                    solve(depth + 1, sum / operand[depth]);
                    break;
            }

            operator[i]++;
        }
    }
}