[SW Expert] 4008. [모의 SW 역량테스트] 숫자 만들기

1) 생각

n개의 숫자와 n-1개의 연산자를 줄 때 만들 수 있는 가장 큰 숫자와 가장 작은 숫자의 차이를 구하여라(연산은 무조건 앞에서 부터 진행한다.)

처음 생각

맨 처음 숫자를 필두로 1개식 연사자를 바꿔가며 모든 경우를 만들어 보면 되므로 재귀로 해결하였다.

2) 방안

1) 재귀의 인자를 4개의 연사자를 다 넣을지 배열로 넣을지 고민하다 그냥 다 넣었다.

2) 재귀에서 가장 중요한 점은 가지치기 이므로 idx를 벗어나지 않도록 idx의 값이 n까지 다달으면 max와 min을 갱신해주고 return 해주었다.

import java.io.IOException;
import java.util.Scanner;
 
public class Solution {
    static int n;
    static int[] arr,num;
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for(int i=1;i<=tc;i++) {
            n = sc.nextInt();
            arr = new int[4];
            num = new int[n];
            for(int j=0;j<4;j++)
                arr[j] = sc.nextInt();
            for(int j=0;j<n;j++)
                num[j] = sc.nextInt();
            max = Integer.MIN_VALUE; min = Integer.MAX_VALUE;
            solve(arr[0],arr[1],arr[2],arr[3],num[0],1);
            System.out.println("#"+i+" "+(max-min));
        }
    }
    
    // + - * /
    private static int max,min;
    private static void solve(int p,int m,int mul,int div,int sum,int idx) {
        if(idx==n) {
            max = Math.max(max,sum);
            min = Math.min(min,sum);
            return;
        }
        
        for(int i=0;i<4;i++) {
            switch(i) {
            case 0:
                if(p>0)    solve(p-1,m,mul,div,sum+num[idx],idx+1);
                break;
            case 1:
                if(m>0) solve(p,m-1,mul,div,sum-num[idx],idx+1);
                break;
            case 2:
                if(mul>0) solve(p,m,mul-1,div,sum*num[idx],idx+1);
                break;
            case 3:
                if(div>0) solve(p,m,mul,div-1,sum/num[idx],idx+1);
                break;
            }
        }
    }
}