[백준] 14888번

사이트

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

14888번: 연산자 끼워넣기

 

문제 

 

분석

필자가 드디어 백트래킹을 마스터했다.! 

 

일단 이 문제는 입력이 아래와 같으면 

2
5 6
0 0 1 0

 

출력은 위에 최대 아래 최소로 나와야 된다. 

30
30

 

즉 입력의 첫째줄은 2는 수의 갯수, 둘째줄은 수를 입력한 것이고, 셋째줄은 = - * / 의 순서로 갯수를 나타낸 것이다. 

 

조건이 나열한 숫자는 이동을 안해도 된다. 즉 백트래킹 방법을 이용해 연산자만 섞어서 최소와 최대 수를 찾으면 된다.

 

static int n;

static int[] num;
static int[] sign;

static int[] result;
static BufferedWriter bw;

static int min = Integer.MAX_VALUE;

static int max = Integer.MIN_VALUE;
static int finalResult;

다음과 같이 static으로 변수들을 선언했다. max를 0으로 안놓은 이유는 음수값이 최대값이 될 수도 있기 때문이다! 

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

    num = new int[n];
    sign = new int[4];
    result = new int[n - 1];

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

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

    bw = new BufferedWriter(new OutputStreamWriter(System.out));
    backTracking(0);
    bw.write(max + "\n" + min);
    bw.flush();
    bw.close();
}

 

익숙한 입력과 출력하는 방법이다. 

 

static int backTracking(int depth) {
    if (depth == n - 1) {
        finalResult = num[0];
        int calculation = calculation();
        max = Math.max(max, calculation);
        min = Math.min(min, calculation);
        return 0;
    }

    for (int i = 0; i < sign.length; i++) {
        if (sign[i] != 0) {
            sign[i] -= 1;
            result[depth] = i;
            backTracking(depth + 1);
            sign[i] += 1;
        }
    }
    return 1;
}

 

백트래킹 함수로 넘어왔다. 차근차근 보자

for (int i = 0; i < sign.length; i++) {
    if (sign[i] != 0) {
        sign[i] -= 1;
        result[depth] = i;
        backTracking(depth + 1);
        sign[i] += 1;
    }
}

여기서 보면 for문 크기를 부호의 크기 까지 줬다. 즉 총 4번 돈다! 

이때 입력한 부호 값이 0 0 1 0 이므로 

만약 0이 아닐때 if문으로 들어오면 들어온 해당 부호는 바로 -1이 되고 result 배열에 참여하게 된다. 

즉 다시말해서 result 배열에 0 1 2 3 1 1 이렇게 있으면 이것은 +, -, *, /, -, - 를 뜻한다! 

이때 우리 result 배열은 현재 2가 있는 것이다! 

 

그리고 다시 재귀함수를 호출해서 

 

if (depth == n - 1) {
    finalResult = num[0];
    int calculation = calculation();
    max = Math.max(max, calculation);
    min = Math.min(min, calculation);
    return 0;
}

위 if문에 걸린다. 왜냐하면 우리는 지금 입력이 5, 6 으로 했기 때문이다(위에 참고!)

그리고 나서 finalResult에 num 배열 즉 num 배열에는 5,6이 저장되어있는데 첫번째 요소인 5를 준다. 

그리고 calculation() 함수로 이동하게 된다. 

public static int calculation() {
    for (int i = 1; i < num.length; i++) {
        if (result[i - 1] == 0) {
            finalResult = finalResult + num[i];
        }
        if (result[i - 1] == 1) {
            finalResult = finalResult - num[i];
        }
        if (result[i - 1] == 2) {
            finalResult = finalResult * num[i];
        }
        if (result[i - 1] == 3) {
            finalResult = finalResult / num[i];
        }
    }

    return finalResult;
}

 

여기서는 이제 계산해주는 함수이다. 

앞서 finalResult에 num배열 첫번째요소를 줘서 여기서는 for이 1로 시작한다. 물론 0으로 시작해도 되지만 필자맘~~  

 

for문을 통해 result 배열에 부호값을 갖고와서 차례되로 계산을 해주면 된다! 

 

그러고 나서 max랑 min 비교해서 출력하면 끝!! 

 

 

 

즉 정리해서 숫자들은 고정이고 부호들만 바꿔서 움직이면 되는 문제다! 

 

 

전체 코드

package backtracking;

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

public class Back14888 {
    static int n;

    static int[] num;
    static int[] sign;

    static int[] result;
    static BufferedWriter bw;

    static int min = Integer.MAX_VALUE;

    static int max = Integer.MIN_VALUE;
    static int finalResult;

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

        num = new int[n];
        sign = new int[4];
        result = new int[n - 1];

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

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

        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        backTracking(0);
        bw.write(max + "\n" + min);
        bw.flush();
        bw.close();
    }

    static int backTracking(int depth) {
        if (depth == n - 1) {
            finalResult = num[0];
            int calculation = calculation();
            max = Math.max(max, calculation);
            min = Math.min(min, calculation);
            return 0;
        }

        for (int i = 0; i < sign.length; i++) {
            if (sign[i] != 0) {
                sign[i] -= 1;
                result[depth] = i;
                backTracking(depth + 1);
                sign[i] += 1;
            }
        }
        return 1;
    }

    public static int calculation() {
        for (int i = 1; i < num.length; i++) {
            if (result[i - 1] == 0) {
                finalResult = finalResult + num[i];
            }
            if (result[i - 1] == 1) {
                finalResult = finalResult - num[i];
            }
            if (result[i - 1] == 2) {
                finalResult = finalResult * num[i];
            }
            if (result[i - 1] == 3) {
                finalResult = finalResult / num[i];
            }
        }

        return finalResult;
    }
}

 

결과

 

느낀점

 

백트래킹 연습문제를 많이 풀어서 그런가 이젠 좀 쉽고 재밌어졌다. 

1시간 걸린 문제였지만 맞았을때 기분이 너무 좋았다! 이 맛에 코테하는거 같다!! 

다음은 이젠 DP다...