[BOJ 14888번] 연산자 끼워넣기 (Java, 완전탐색, 재귀호출)알고리즘/완전 탐색2023. 6. 13. 12:34
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/14888
풀이
- DFS로 연산자에 대한 순열(Permutation)을 구한 후 연산 결과값 구함
- N(2 ≤ N ≤ 11) 이므로 최대 연산자 개수는 10개, 순열 10! = 3,628,800
- 시간복잡도 O(N! * N ) = O(10! * 11) = 약 3,600만번 이므로 풀이가능
제출 코드
풀이1. 연산자 순열을 구한 후 연산 처리
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N;
static int MAX_VALUE = Integer.MIN_VALUE;
static int MIN_VALUE = Integer.MAX_VALUE;
static int[] operand;
static int[] operator;
static int[] selected;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
operand = new int[N];
for(int i = 0; i < N; i++) {
operand[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
operator = new int[4];
for(int i = 0; i < 4; i++) {
operator[i] = Integer.parseInt(st.nextToken());
}
selected = new int[N - 1]; // 연산자 개수 = 피연산자 개수 -1
br.close();
}
static int cal(int v1, int v2, int _op) {
int result = 0;
switch(_op) {
case 0 : {
result = v1 + v2;
break;
}
case 1 : {
result = v1 - v2;
break;
}
case 2 : {
result = v1 * v2;
break;
}
case 3 : {
result = v1 / v2;
break;
}
}
return result;
}
static void dfs(int cnt) {
if(cnt == N - 1) {
int result = operand[0];
for(int i = 1; i < N; i++) {
result = cal(result, operand[i], selected[i - 1]);
}
MAX_VALUE = Math.max(MAX_VALUE, result);
MIN_VALUE = Math.min(MIN_VALUE, result);
return;
}
for(int i = 0; i < 4; i++) {
if(operator[i] == 0) continue;
operator[i] -= 1;
selected[cnt] = i;
dfs(cnt + 1);
selected[cnt] = 0;
operator[i] += 1;
}
}
static void pro() {
dfs(0);
sb.append(MAX_VALUE).append("\n").append(MIN_VALUE);
System.out.println(sb);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
풀이2.
https://gksdudrb922.tistory.com/33
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, ADD, SUB, MUL, DIV;
static int MAX_VALUE = Integer.MIN_VALUE;
static int MIN_VALUE = Integer.MAX_VALUE;
static int[] operand;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
operand = new int[N];
for(int i = 0; i < N; i++) {
operand[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < 4; i++) {
int value = Integer.parseInt(st.nextToken());
if(i == 0) ADD = value;
else if(i == 1) SUB = value;
else if(i == 2) MUL = value;
else DIV = value;
}
br.close();
}
static void dfs(int idx, int data) {
if(idx == N) {
MIN_VALUE = Math.min(MIN_VALUE, data);
MAX_VALUE = Math.max(MAX_VALUE, data);
} else {
// +
if(ADD > 0) {
ADD -= 1;
dfs(idx + 1, data + operand[idx]);
ADD += 1;
}
// -
if(SUB > 0) {
SUB -= 1;
dfs(idx + 1, data - operand[idx]);
SUB += 1;
}
// *
if(MUL > 0) {
MUL -= 1;
dfs(idx + 1, data * operand[idx]);
MUL += 1;
}
// /
if(DIV > 0) {
DIV -= 1;
dfs(idx + 1, data / operand[idx]);
DIV += 1;
}
}
}
static void pro() {
dfs(1, operand[0]);
sb.append(MAX_VALUE).append("\n").append(MIN_VALUE);
System.out.println(sb);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
풀이3. 순열을 구할 때 매번 연산 결과를 넘기는 방식
- 마지막 if(k == N - 1) 일 때 N만큼 순회하면 연산하지 않아도 되니, 속도 개선됨
- 시간복잡도 : O(10!)
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int MIN_VALUE, MAX_VALUE;
static int[] data;
static int[] operator;
static StringBuilder sb;
public static void input() {
InputProcessor inputProcessor = new InputProcessor();
N = inputProcessor.nextInt();
data = new int[N];
for(int i = 0; i < N; i++) {
data[i] = inputProcessor.nextInt();
}
operator = new int[4];
for(int i = 0; i < 4; i++) {
operator[i] = inputProcessor.nextInt();
}
sb = new StringBuilder();
MAX_VALUE = Integer.MIN_VALUE;
MIN_VALUE = Integer.MAX_VALUE;
}
public static void output() throws IOException {
sb.append(MAX_VALUE).append("\n").append(MIN_VALUE);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(sb.toString());
bw.flush();
bw.close();
}
public static void main(String[] args) throws IOException {
input();
rec(0, data[0]);
output();
}
private static void rec(int k, int value) {
if(k == N - 1) {
MAX_VALUE = Math.max(MAX_VALUE, value);
MIN_VALUE = Math.min(MIN_VALUE, value);
return;
}
for(int i = 0; i < 4; i++) {
if(operator[i] == 0) continue;
operator[i] -= 1;
rec(k + 1, calculate(value, i, data[k + 1]));
operator[i] += 1;
}
}
private static int calculate(int oprand1, int operator, int oprand2) {
int result = oprand1;
if(operator == 0) {
result += oprand2;
} else if(operator == 1) {
result -= oprand2;
} else if(operator == 2) {
result *= oprand2;
} else if(operator == 3) {
result /= oprand2;
}
return result;
}
public static class InputProcessor {
BufferedReader br;
StringTokenizer st;
public InputProcessor() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public String next() {
while(st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
}
반응형
'알고리즘 > 완전 탐색' 카테고리의 다른 글
[BOJ20166] 문자열 지옥에 빠진 호석 (완전탐색, DFS) (0) | 2023.08.31 |
---|---|
[BOJ20164] 홀수 홀릭 호석 (완전탐색) (0) | 2023.08.30 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!