πŸ“– [λ°±μ€€μ•Œκ³ λ¦¬μ¦˜ 풀이] Q.14888 μ—°μ‚°μž λΌμ›Œλ„£κΈ° 문제 풀이 - java

πŸ“– 문제

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

N개의 수둜 이루어진 μˆ˜μ—΄ A1, A2, …, AN이 주어진닀. 또, μˆ˜μ™€ 수 사이에 λΌμ›Œλ„£μ„ 수 μžˆλŠ” N-1개의 μ—°μ‚°μžκ°€ 주어진닀.

μ—°μ‚°μžλŠ” λ§μ…ˆ(+), λΊ„μ…ˆ(-), κ³±μ…ˆ(Γ—), λ‚˜λˆ—μ…ˆ(Γ·)으둜만 이루어져 μžˆλ‹€.

μš°λ¦¬λŠ” μˆ˜μ™€ 수 사이에 μ—°μ‚°μžλ₯Ό ν•˜λ‚˜μ”© λ„£μ–΄μ„œ, μˆ˜μ‹μ„ ν•˜λ‚˜ λ§Œλ“€ 수 μžˆλ‹€. μ΄λ•Œ, 주어진 수의 μˆœμ„œλ₯Ό λ°”κΎΈλ©΄ μ•ˆ λœλ‹€.

예λ₯Ό λ“€μ–΄, 6개의 수둜 이루어진 μˆ˜μ—΄μ΄ 1, 2, 3, 4, 5, 6이고, 주어진 μ—°μ‚°μžκ°€

λ§μ…ˆ(+) 2개, λΊ„μ…ˆ(-) 1개, κ³±μ…ˆ(Γ—) 1개, λ‚˜λˆ—μ…ˆ(Γ·) 1개인 κ²½μš°μ—λŠ” 총 60κ°€μ§€μ˜ 식을 λ§Œλ“€ 수 μžˆλ‹€. 예λ₯Ό λ“€μ–΄, μ•„λž˜μ™€ 같은 식을 λ§Œλ“€ 수 μžˆλ‹€.

1+2+3-4Γ—5Γ·6 1Γ·2+3+4-5Γ—6 1+2Γ·3Γ—4-5+6 1Γ·2Γ—3-4+5+6 μ‹μ˜ 계산은 μ—°μ‚°μž μš°μ„  μˆœμœ„λ₯Ό λ¬΄μ‹œν•˜κ³  μ•žμ—μ„œλΆ€ν„° 진행해야 ν•œλ‹€. 또, λ‚˜λˆ—μ…ˆμ€ μ •μˆ˜ λ‚˜λˆ—μ…ˆμœΌλ‘œ λͺ«λ§Œ μ·¨ν•œλ‹€.

음수λ₯Ό μ–‘μˆ˜λ‘œ λ‚˜λˆŒ λ•ŒλŠ” C++14의 기쀀을 λ”°λ₯Έλ‹€. 즉, μ–‘μˆ˜λ‘œ λ°”κΎΌ λ’€ λͺ«μ„ μ·¨ν•˜κ³ , κ·Έ λͺ«μ„ 음수둜 λ°”κΎΌ 것과 κ°™λ‹€.

이에 λ”°λΌμ„œ, μœ„μ˜ 식 4개의 κ²°κ³Όλ₯Ό 계산해보면 μ•„λž˜μ™€ κ°™λ‹€.

1+2+3-4Γ—5Γ·6 = 1 1Γ·2+3+4-5Γ—6 = 12 1+2Γ·3Γ—4-5+6 = 5 1Γ·2Γ—3-4+5+6 = 7 N개의 μˆ˜μ™€ N-1개의 μ—°μ‚°μžκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, λ§Œλ“€ 수 μžˆλŠ” μ‹μ˜ κ²°κ³Όκ°€ μ΅œλŒ€μΈ 것과 μ΅œμ†ŒμΈ 것을 κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

πŸ” 접근법

Q.14888 μ—°μ‚°μž λΌμ›Œλ„£κΈ° λ¬Έμ œμž…λ‹ˆλ‹€.

μ£Όμ–΄μ§€λŠ” μˆ˜μ—΄μ—

주어진 μ—°μ‚°μžλ“€μ„ λͺ¨λ‘ μ΄μš©ν•΄λ‚˜μ˜€λŠ”

λͺ¨λ“  경우의 μˆ˜μ‹μ—μ„œ μ‹μ˜ κ²°κ³Όκ°€ μ΅œλŒ€μΈ 것과 μ΅œμ†ŒμΈ 것을 κ΅¬ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€.

단, μ—¬κΈ°μ„œ μ£Όμ–΄μ§€λŠ” 수의 μˆœμ„œλŠ” 고정이고

μ—°μ‚°μžμ΄ μš°μ„ μˆœμœ„ λ˜ν•œ λͺ¨λ‘ λ™λ“±ν•©λ‹ˆλ‹€.

λͺ¨λ“  경우의 μˆ˜μ‹μ„ 확인해봐야 ν•˜κΈ° λ•Œλ¬Έμ—

λͺ¨λ“  경우λ₯Ό ν™•μΈν•˜λŠ” brtue force λ°©μ‹μœΌλ‘œ 풀이가 κ°€λŠ₯ν•©λ‹ˆλ‹€.

각 μ—°μ‚°μžλ₯Ό λ°±νŠΈλž˜ν‚Ήμ„ 톡해 λͺ¨λ‘ λ„£μ–΄

μ™„μ„± 된 μ‹μ˜ κ²°κ³Όκ°’λ“€μ˜

μ΅œλŒ€κ°’κ³Ό μ΅œμ†Ÿκ°’μ„ κ΅¬ν•˜λ©΄ 닡을 λ„μΆœν•  수 μžˆμŠ΅λ‹ˆλ‹€.

πŸ’» μ½”λ“œ

package problem.brute;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main_14888 {

    static int n;
    static int[] numbers;
    static int[] operators;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        input();
        go(1, numbers[0]);
        System.out.println(max);
        System.out.println(min);
    }


    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        numbers = new int[n];
        operators = new int[4];
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(input[i]);
        }
        String[] temp = br.readLine().split(" ");
        for (int i = 0; i < 4; i++) {
            int count = Integer.parseInt(temp[i]);
            operators[i] = count;
        }
    }

    public static void go(int index, int number) {
        if (index == n) {
            max = Math.max(max, number);
            min = Math.min(min, number);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (operators[i] > 0) {
                operators[i]--;
                if (i == 0) {
                    go(index + 1, number + numbers[index]);
                }
                if (i == 1) {
                    go(index + 1, number - numbers[index]);
                }
                if (i == 2) {
                    go(index + 1, number * numbers[index]);
                }
                if (i == 3) {
                    go(index + 1, number / numbers[index]);
                }
                operators[i]++;
            }
        }
    }
}

Written on March 3, 2021