![[백준,BOJ 14888] 연산자 끼워넣기(JAVA 구현,추가풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FYUsAm%2FbtqzZ3hAdqC%2F98BJwclWG0k3B0QcNj0CPk%2Fimg.png)
반응형
-내 생각
단계별로 풀어보기를 통해서 접한 첫 번째 기출문제였다. 스도쿠와 N-Queen 문제 때문인지 문제의 난이도는 그렇게 높다고 느껴지지 않았다. 그러나 문제를 푸는 동안 시행착오가 한 번 있었는데, 최댓값과 최솟값을 비교하기 위해서는 모든 연산자를 경우의 수에 따라 전부 대입해보아야 했는데, 처음에는 하나의 연산자를 넣어 비교하는 방식을 이용해보려 했다. 예를 들어 예제 입력 3번의 경우에서 1과 2를 각 연산자로 한 번만 계산 후 대소 비교를 생각했었는데, 힌트를 보고 틀린 생각이란 것을 알 수 있었다. 최댓값의 경우가 1과 2 사이의 연산자가 -인데, 앞선 방식으로 풀면 x일 때가 최댓값의 경우라고 가정하게 되는 것이다. 즉, 결과적으로는 모든 연산자를 각 경우의 수에 따라 대입해 최종 값을 통해 최댓값과 최솟값을 구해야 한다는 것이다. 이 말은 즉 완전 탐색을 통해 모든 경우의 수를 알아보아야 한다는 뜻이다.
-해법
코드 자체는 간단하므로 코드를 통해서 확인해 보자.
import java.util.*;
public class Main {
static int n; // n개의 숫자 입력
static int check[],cal[]; // 0:덧셈, 1:뺄셈, 2:곱셉, 3:나눗셈
static int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE; // 최댓값과 최솟값을 저장 할 변수
static void dfs(int num,int idx) { // 최초 첫 번째 숫자, 1번 인덱스가 전달
if(idx == n) { // DFS 종료 부, 마지막 인덱스에서 재귀호출을 실행하면 이 부분에서 걸린다.
if(num>max) { // 최종적인 결과 값이 num값에 저장되므로 최댓값과 최솟값을 찾는다.
max = num;
}
if(num < min) {
min = num;
}
return ;
}
int result = 0; // 한 번의 연산자를 사용한 결과가 저장 될 변수
for(int j=0;j<4;j++) { // 연산자 배열을 탐색
if(cal[j]!=0) { // 연산자가 존재하는 경우
cal[j]--; // 해당 연산자의 값을 -1 해준다.
switch(j) { // 각 연산자에 맞는 케이스로 이동
case 0:
result = num +check[idx];
break;
case 1:
result = num - check[idx];
break;
case 2:
result = num * check[idx];
break;
case 3:
if(num <0 && check[idx]>0) { // 음수를 양수로 나누는 경우에는
num*=-1; // 음수를 양수로 바꾼 뒤
result = num / check[idx]; // 몫을 취하고
result*=-1; // 해당 몫을 음수화
}else {
result = num / check[idx]; // 일반적인 경우에는 몫만 취하게 된다.
break;
}
}
dfs(result,idx+1); // 연산의 결과와 인덱스를 증가시켜 전달
cal[j]++; // 한 번의 경우를 모두 탐색한 후에는 다시 감소시켰던 연산자 값을 +1, 백 트래킹
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
check = new int[n]; // 숫자가 저장 될 배열을 할당.
cal = new int[4]; // 연산자가 저장 될 배열을 할당.
for(int i=0;i<n;i++) { // 숫자 입력
check[i] = sc.nextInt();
}
for(int i=0;i<4;i++) { // 연산자 입력
cal[i] = sc.nextInt();
}
dfs(check[0],1); // DFS 호출
System.out.println(max);
System.out.println(min);
}
}
이전의 풀이와 다르지 않다. 모든 연산자를 하나씩 바꿔가며 최종 결과에서 최댓값과 최솟값을 찾으면 된다. 코드는 좀 더 간단하게 만들었다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
class Main {
static BufferedReader br;
static BufferedWriter bw;
static int max = Integer.MIN_VALUE;
static int min = Integer.MAX_VALUE;
// DFS 메소드
static void dfs(int[] a,int[] ins,int num,int idx) {
// 종료 부, idx값이 마지막 데이터를 넘어서면 최댓값과 최솟값을 찾는다.
if(idx == a.length) {
max = Math.max(num,max);
min = Math.min(num, min);
return;
}
for(int i=0;i<ins.length;i++) {
if(ins[i] != 0) { // 연산자가 존재한다면,
// 값을 감소시키고,
ins[i]--;
/*
0: +
1: -
2: *
3: /
*/
// 맞는 연산자에 따라 깊이 우선 탐색을 수행.
switch(i) {
case 0: dfs(a,ins,num+a[idx],idx+1); break;
case 1: dfs(a,ins,num-a[idx],idx+1); break;
case 2: dfs(a,ins,num*a[idx],idx+1); break;
case 3: dfs(a,ins,num/a[idx],idx+1); break;
}
// DFS 종료 후, 원래 상태로 돌린다.
ins[i]++;
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int a[] = new int[n]; // 데이터 배열
int ins[] = new int[4]; // 연산자 배열
// 데이터 입력
st = new StringTokenizer(br.readLine());
for(int i=0;i<a.length;i++) {
a[i] = Integer.parseInt(st.nextToken());
}
// 연산자 입력
st = new StringTokenizer(br.readLine());
for(int i=0;i<ins.length;i++) {
ins[i] = Integer.parseInt(st.nextToken());
}
// DFS 수행
dfs(a,ins,a[0],1);
// bw.write() 써야 되는데 깜빡했다.
System.out.println(max);
System.out.println(min);
}
}
반응형