SWEA[4008] - 숫자 만들기

링크

SWEA[4008]

문제설명

• 중복조합 + 시뮬

문제풀이

• 중복조합(조합에 count조건만 넣어주면 중복조합임) + 시뮬

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution4008 {

    public static int[] oper;
    public static int[] n_oper;
    public static int[] num;
    public static int Max=Integer.MIN_VALUE;
    public static int Min=Integer.MAX_VALUE;
    public static int Temp;
    public static int N;

    public static int operation(int a, int b, int oper) {
        switch (oper) {
        case 0:
            return a+b;
        case 1:
            return a-b;
        case 2:
            return a*b;
        case 3:
            return a/b;
        }
        return -1;
    }

    public static void Simulation() {

        Temp = operation(num[0], num[1], n_oper[0]);
        for (int i = 1; i < N-1; i++) {
            Temp = operation(Temp,num[i+1],n_oper[i]);
        }

    }

    public static void Search(int cnt) { 
        if(cnt==N-1) {
            Temp=0;
            Simulation();
//            System.out.println(Arrays.toString(n_oper));
            Max = Math.max(Max, Temp);
            Min = Math.min(Min, Temp);
        }
        for (int i = 0; i < 4; i++) {
            if(oper[i]>0) {
                n_oper[cnt]=i;
                oper[i]--;
                Search(cnt+1);
                n_oper[cnt]=-1;
                oper[i]++;
            }
        }
    }

    public static void main(String args[]) throws Exception
    {
        System.setIn(new FileInputStream("res/swea/4008.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T;
        T=Integer.parseInt(br.readLine());

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = Integer.parseInt(br.readLine());
            oper = new int[4];
            num = new int[N];
            n_oper = new int[N-1];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 4; i++) {
                oper[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                num[i] = Integer.parseInt(st.nextToken());
            }

            Search(0);

            System.out.println("#"+test_case+" "+(Max-Min));
//            초기화
            Max=Integer.MIN_VALUE;
            Min=Integer.MAX_VALUE;
        }
    }
}

아쉬운점

• -

잘한점

• 조합->중복조합