백준 14888번 : 연산자 끼워넣기 (JAVA) 문제 풀이

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

---

 

 

---

문제 분석

처음의 연산할 숫자의 개수가 주어지고, 둘째 줄에는 연산할 수, 셋째 줄에는 연산자의 개수가 주어진다.

 

예를 들어 입출력 2를 보면,

3
3 4 5
1 0 1 0

연산자는 + , x  각 1개씩 사용 가능하다.

모든 경우의 연산을 보면,

3 + 4 x 5 = 35
3 x 4 + 5 = 17

결과가 35, 17인 두가지 경우가 나온다.

 

먼저 재귀 함수 부분 코드를 살펴보자.

static void dfs(int depth, int sum) {

     /* 종료 조건 */
     if (depth == N) {
         if (MAX < sum)  MAX = sum;		// 왜 if-if 로 구현 했는가?
         if (MIN > sum)  MIN = sum;		// 만약, 결과 값이 2, 3, 4 순으로 온다면 if-else로 구현했다면, MAX 값만 변경 되면서 MIN값이 제대로 안들어 갔을 것이다.
         return;
     }

     for (int i = 0; i < N - 1; i++) {
         int cur = numbers[depth];		// 함수의 깊이에 따라 숫자를 뽑는다.
         if (!isUsed[i]) {			// 연산자를 사용한 적이 있는지 확인
             isUsed[i] = true;			// 만약 없다면, 해당 연산자를 사용했다고 체크!
             int result = calc(sum, cur, operators[i]);	// 계산 식으로 이동.
             dfs(depth + 1, result);		// 재귀 호출 부분(깊이+1, 계산한 결과 값(result)를 전달)
             isUsed[i] = false;			// 재귀 호출이 모두 끝났다고 생각하고, 다시 비 방문 처리.
         }
     }
 }

재귀의 깊이(depth)로 연산할 숫자의 배열 인덱스로 사용하고, 재귀 함수 안에 for문으로 연산자 배열을 체크하면서, 계산을 해서 다시 재귀 호출을 하면서 파라미터로 (깊이, 연산한 결과 값) 를 넘겨준다.

 

연산하는 calc 함수 구현

static int calc(int sum, int num, String oper) {

	switch (oper) {
		case "+":   sum += num;   break;
		case "-":   sum -= num;   break;
		case "*":   sum *= num;   break;
		case "/":   sum /= num;   break;
	}
	return sum;
}

 

switch 문으로 파라미터로 넘어온 연산자(oper) 문자열에 따라 연산 결과를 리턴 한다.

 

전체 코드

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

public class Main {
    static int MAX = Integer.MIN_VALUE; // 최대값
    static int MIN = Integer.MAX_VALUE; // 최소값
    static String[] operators;          // 연산자 배열
    static boolean[] isUsed;            // 연산자 사용 여부 체크
    static int[] numbers;               // 계산할 숫자 배열
    static int N;                       // 숫자 개수

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(bf.readLine());
        numbers = new int[N];
        operators = new String[N-1];
        isUsed = new boolean[N];

        /* numbers 받기 */
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        /* operators 받기 */
        int index = 0;
        String oper = "+-*/";
        st = new StringTokenizer(bf.readLine());

        for (int i = 0; i < 4; i++) {
            int n = Integer.parseInt(st.nextToken());
            if (n > 0) {
                String op = oper.substring(i, i + 1);
                while (n-- > 0) {
                    operators[index++] = op;
                }
            }
        }        

        dfs(1, numbers[0]);

        System.out.println(MAX);
        System.out.println(MIN);
    }

    static void dfs(int depth, int sum) {

        /* 종료 조건 */
        if (depth == N) {
            if (MAX < sum)  MAX = sum;
            if (MIN > sum)  MIN = sum;
            return;
        }

        for (int i = 0; i < N - 1; i++) {
            int cur = numbers[depth];
            if (!isUsed[i]) {
                isUsed[i] = true;
                int result = calc(sum, cur, operators[i]);
                dfs(depth + 1, result);
                isUsed[i] = false;
            }
        }
    }

    static int calc(int sum, int num, String oper) {
        switch (oper) {
            case "+":   sum += num;   break;
            case "-":   sum -= num;   break;
            case "*":   sum *= num;   break;
            case "/":   sum /= num;   break;
        }
        return sum;
    }
}