BJ S1 14888 연산자끼워넣기

BJ S1 14888 연산자 끼워넣기

 

 

문제링크

http://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/ok9Pakfkd70

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.silver.l1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_S1_14888_연산자끼워넣기 {

    static StringBuilder output = new StringBuilder();
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    // 피 연산자들
    static int[] nums;

    // 연산자들
    static int[] opers;

    // 구해야할 값: 최대, 최소 값
    static long Max = Long.MIN_VALUE, Min = Long.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));

        // 숫자 입력 처리
        int numCnt = Integer.parseInt(input.readLine());
        nums = new int[numCnt];

        StringTokenizer tokens = new StringTokenizer(input.readLine());
        for (int i = 0; i < numCnt; i++) {
            nums[i] = Integer.parseInt(tokens.nextToken());
        }

        // 연산자 입력 처리
        tokens = new StringTokenizer(input.readLine());
        int sum = 0;
        int p = Integer.parseInt(tokens.nextToken());
        int s = Integer.parseInt(tokens.nextToken());
        int m = Integer.parseInt(tokens.nextToken());
        int d = Integer.parseInt(tokens.nextToken());

        sum = p + s + m + d;
        opers = new int[sum];

        int i = 0;
        for (int j = 0; j < p; j++) {
            opers[i++] = 1;
        }
        for (int j = 0; j < s; j++) {
            opers[i++] = 2;
        }
        for (int j = 0; j < m; j++) {
            opers[i++] = 3;
        }
        for (int j = 0; j < d; j++) {
            opers[i++] = 4;
        }
        // 입력 확인
        // System.out.println(Arrays.toString(opers));
        do {
            // 순열 확인
            // System.out.println(Arrays.toString(opers));
            long base = nums[0];
            for (i = 0; i < sum; i++) {
                int oper = opers[i];
                if (oper == 1) {
                    base += nums[i + 1];
                } else if (oper == 2) {
                    base -= nums[i + 1];
                } else if (oper == 3) {
                    base *= nums[i + 1];
                } else {
                    base /= nums[i + 1];
                }
            }

            Min = Math.min(Min, base);
            Max = Math.max(Max, base);
        } while (nextPermutation(opers));

        output.append(Max).append("\n").append(Min).append("\n");
        System.out.println(output);
    }

    static boolean nextPermutation(int[] opers) {
        int i, j;
        // 뒤에서 부터 연이은 요소들 중 뒤보다 앞이 더 작은 첫 번째 녀석의 인덱스 i를 찾는다.
        for (i = opers.length - 2; i >= 0; i--) {
            if (opers[i] < opers[i + 1]) {
                break;
            }
        }
        // 그런 경우가 없다면 마지막 상태
        if (i < 0) {
            return false;
        }

        // 역시 뒤에서 부터 i번째 요소보다 큰 j 번째 요소를 찾는다.
        for (j = opers.length - 1; j >= 0; j--) {
            if (opers[i] < opers[j]) {
                break;
            }
        }
        // i와 j를 스윕한다.
        swap(i, j, opers);

        // i 뒤의 요소들을 전체적으로 swap 한다.
        for (int m = i + 1, n = opers.length - 1; m < n; m++, n--) {
            swap(m, n, opers);
        }

        return true;
    }

    static void swap(int a, int b, int[] src) {
        int temp = src[a];
        src[a] = src[b];
        src[b] = temp;
    }

    private static String src = "6\r\n" +
                                "1 2 3 4 5 6\r\n" +
                                "2 1 1 1";
}