π [λ°±μ€μκ³ λ¦¬μ¦ νμ΄] 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]++;
}
}
}
}