[Baekjoon 15658번] 연산자 끼워넣기(2) 문제 (with 자바)

문제

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

15658번: 연산자 끼워넣기 (2)

 

 

 

 

풀어보기전에, 아래 문제를 먼저 풀어보자.

백준 14888번_연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

백준 14888번_아래 해결코드를 참고하자.

https://devfunny.tistory.com/513

[Baekjoon 14888번] 연산자 끼워넣기 문제 (with 자바)

 

비교

dfs 함수에 아래 코드가 추가되었다.

 

/* value 가 배열의 길이보다 커지는 시점엔 반복문 탈출 */
if (value > arr.length - 1) {
	break;
}

 

문제를 살펴보면, 14888번_연산자 끼워넣기 문제에서는 제공되는 식의 조건이 다음과 같다.

N개의 수와 N-1개의 연산자가 주어졌을 때,

 

그리고 현재 포스팅의 문제인 15658번_연산자 끼워넣기(2) 문제에서는 제공되는 식의 조건이 다음과 같다.

모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다.

따라서 value 가 현재 입력받은 배열 arr의 길이보다 커질 경우 반복문을 탈출해야한다.

 

 

 

 

풀이코드

package seohae.algorithm.level2;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * https://www.acmicpc.net/problem/15658
 */
public class Problem_017_15658 {
    public static int[] arr;
    static int[] opArr;
    static int N; /* 열 개수 */
    public static ArrayList<Integer> resultList = new ArrayList<Integer>();

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 열 개수
        arr = new int[N];
        opArr = new int[4];

        for(int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        for(int i = 0; i < 4; i++) {
            opArr[i] = sc.nextInt();
        }

        dfs(1, arr[0]); // 출발 시작

        int max = resultList.stream()
                            .mapToInt(x -> x)
                            .max().getAsInt();

        int min = resultList.stream()
                            .mapToInt(x -> x)
                            .min().getAsInt();

        System.out.println(max); /* 최대값 */
        System.out.println(min); /* 최소값 */
    }

    static void dfs(int value, int sum) {

        for (int i = 0; i < 4; i++) {
            /* value 가 배열의 길이보다 커지는 시점엔 반복문 탈출 */
            if (value > arr.length - 1) {
                break;
            }

            if (opArr[i] != 0) {
                opArr[i]--; /* 연산자 사용 */

                if (i == 0) {
                    dfs(value + 1, sum + arr[value]);
                } else if (i == 1) {
                    dfs(value + 1, sum - arr[value]);
                } else if (i == 2) {
                    dfs(value + 1, sum * arr[value]);
                } else if (i == 3) {
                    dfs(value + 1, sum / arr[value]);
                }

                opArr[i]++; /* 다시 롤백 */
            }
        }

        if (value == N) { /* 식이 완성되었음 */
            resultList.add(sum);
        }
    }
}