[백준][JAVA알고리즘]14888번 풀이(연산자 끼워넣기) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 14888번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 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개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2,..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워 넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

입력 예시

2
5 6
0 0 1 0

출력 예시

30
30

입력 예시

 

3
3 4 5
1 0 1 0

출력 예시

35
17

입력 예시

 

6
1 2 3 4 5 6
2 1 1 1

출력 예시

54
-24

성공코드

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

public class Main {

	static int N;
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	static ArrayList<Integer> num = new ArrayList<>();
	static ArrayList<Integer> opr = new ArrayList<>();

	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer str1 = new StringTokenizer(br.readLine());
		StringTokenizer str2 = new StringTokenizer(br.readLine());
		
		for(int i = 0 ; str1.hasMoreTokens();i++) {
			num.add(Integer.parseInt(str1.nextToken()));
		}
		
		for(int i = 0 ; str2.hasMoreTokens();i++) {
			opr.add(Integer.parseInt(str2.nextToken()));
		}

		dfs(num.get(0), 1);
		
		System.out.println(max);
		System.out.println(min);
		
}
	public static void dfs(int a, int depth) {
		
		if(depth == N) {
			max = Math.max(max, a);
			min = Math.min(min, a);
			return;
		}
		
		for(int i = 0 ; i < 4 ; i++) {
			if(opr.get(i)>0) {
				opr.set(i, opr.get(i)-1);
				
				switch(i) {
					case 0:dfs(a+num.get(depth), depth+1);	break;
					case 1:dfs(a-num.get(depth), depth+1);	break;
					case 2:dfs(a*num.get(depth), depth+1);	break;
					case 3:dfs(a/num.get(depth), depth+1);	break;
				}
				
				opr.set(i, opr.get(i)+1);
			}
		}	
	}

}

역시나 이번에 백 트레킹 문제도 역시나 헤매면서 여러 코드를 이해하고 풀이해볼 수 있었습니다 ㅜㅜ 이번 문제의 핵심은 말 그대로 연산자를 하나씩 끼워 넣는 문제입니다.

 

문제가 길어서 간단히 요약해서 말해드리자면,

2번째 예시

3

3 4 5

1 0 1 0

을 생각해보면 됩니다. 숫자는 3개 3 4 5입니다. 거기에 연산자는 + 1개 // * 1개

숫자 3개와 연산자 2개를 이용해서 최댓값과 최솟값을 찾아내면 되는 문제였습니다. 곰곰이 생각해보면 해당 문제는 모든 경우의 수를 다 계산해야 하는 문제 입을 느낄 수 있었습니다. 해당 문제를 어떻게 풀이하고 이해하는지 STEP을 따라 이해시켜 드리겠습니다.

---

알고리즘 흐름도

입력받기 -> DFS로 연산한 값을 계속하여 넣어준다. -> 깊이는 1부터 시작

---

STEP1 코드 기본 구성

static int N;
static int max = Integer.MIN_VALUE;
static int min = Integer.MAX_VALUE;
static ArrayList<Integer> num = new ArrayList<>();
static ArrayList<Integer> opr = new ArrayList<>();
    
StringTokenizer str1 = new StringTokenizer(br.readLine());
StringTokenizer str2 = new StringTokenizer(br.readLine());

N : 가장 먼저 받는 변수로 배열이나 얼마나 반복을 할지 알려주는 역학을 한다.

max, min : 우리가 결과로 출력할 최댓값, 최솟값을 담을 변수 역할을 한다.

num, opr : 각각 숫자와 연산자를 담는 ArrayList이다. (여기서 배열로 선언해도 크게 상관이 없다.

str1, str2 : 각각 숫자와 연산자를 입력받아 "공백"을 기준으로 나누어 num, opr에 값을 넣어주는 역할을 한다.

---

STEP2 DFS FOR문의 이해

이 부분이 사실 dfs의 핵심이라고 볼 수 있습니다. 이 부분을 얼마나 잘 짜느냐가 dfs의 결과를 좌우하게 된다는 것을 알 수 있죠.

 

그러면 저희는 이번 dfs에는 어떠한 방식으로 구현을 할지 생각해 봐야 합니다. 어떠한 것을 depth로 지정할 것인가. dfs의 인자로 무엇을 받아야 하는가입니다.

 

 - 어떠한 것을 depth로 지정할 것인가?

이 부분으로 저도 항상 고민을 합니다. 여기서는 숫자, 연산자, 결괏값(최소, 최대) 이 정도가 되겠네요. 그런데 이때 결괏값은 depth로 지정할 수 없다는 것을 알 것입니다. 왜냐하면, 어떻게 될지 저희가 예측하기 힘들기 때문이죠. 그러면 이제 숫자와 연산자 중에 어떠한 것을 depth로 잡을지 고민해야 합니다. 헷갈리신다면, 하나씩 대입하여 풀어보시면 되지만, 저희들은 숫자로 지정하겠습니다. (왜냐하면, 3 + 4 * 5 이런 식으로 진행된다면 마지막은 숫자가 될 테니깐요 // 그냥 간단히 마지막에 끝나야 하는 것을 depth로 잡았습니다.)

 

 - dfs의 인자는 무엇으로 지정할 것인가.

여기서 저희는 1가지는 알 수 있죠. depth 즉, 숫자들의 인덱스를 넣어주면 됩니다. 흠... 그다음은 사실 저도 해당 문제에서 해결하지 못하여 다른 분들의 코드를 살펴보며 이해했었죠. 여기서 인자로 넣어줄 값은 바로 연산된 값! 을 인자로 넣어주어 쉽게 풀이할 수 있다는 것을 알 수 있었죠.

(이 부분은 많은 문제를 풀어보거나, 일단은 depth만 인자로 지정하여 풀면서 풀이 도중에 넣어주는 방식으로 많이들 구현을 하십니다.) 모두가 처음부터 문제를 보자마자 "아! 결괏값을 넣어주어야겠구나"라는 생각을 하지 못합니다. 많은 알고리즘 경험이 있거나, 풀이 도중에 인자를 추가하여하는 경우가 대부분이죠

 

public static void main(String[] args) throws IOException {
		...
		dfs(num.get(0), 1);		
        ...
}

public static void dfs(int a, int depth) {
		for(int i = 0 ; i < 4 ; i++) {
			if(opr.get(i)>0) {
				opr.set(i, opr.get(i)-1);
				
				switch(i) {
					case 0:dfs(a+num.get(depth), depth+1);	break;
					case 1:dfs(a-num.get(depth), depth+1);	break;
					case 2:dfs(a*num.get(depth), depth+1);	break;
					case 3:dfs(a/num.get(depth), depth+1);	break;
				}
				
				opr.set(i, opr.get(i)+1);
			}
		}	
	}

이번에는 2번째 입력 예시로 보여드리겠습니다. 3 4 5와 +, *의 연산자를 이용하여 풀이하는 방식이죠. 처음 인자로 3과 1을 넣어줍니다.

 

for문의 핵심은 바로 4번 반복 이 의미는 각 연산자의 크기만큼 사용한다는 의미이죠. 차근차근 이해해보죠 i가 0~3까지 반복을 하죠.

i=0 -> 만약 opr의 0번째 인덱스에 값이 0 이상이라면(즉 1 0 1 0에서 +의 연산자가 있냐를 물어보는 거죠), opr에 + 값이 있으면 그 값을 -1을 해주어 1개의 +를 을 소진해주죠 opr의 값은 0 0 1 0으로 변경이 되겠죠.

만약 switch(0)의 값이 0이면 3에 4의 값을 +을 해주고, 그 값을 dfs(7,2)를 넣어줍니다.

그 후 다시 opr의 + 값을 다시 1을 더해줍니다. (왜냐면 제일 처음에 +가 아니라 *의 값이 올 수 있도록 해주기 위해서죠

 

i=1일 경우는 if문에 걸리는 값이 없어서 pass

 

i=2일 경우 if문에 걸리므로 dfs에 dfs(3*4,2) 즉 dfs(12,2)가 들어가게 됩니다.

 

그 이후의 i는 모두 if문에 걸리지 않으므로 자연스럽게 끝나게 되죠.

 

그렇게 되면 이제 저희가 생각해 볼 수 있는 것은 dfs(7,2)와 dfs(12,2)가 됩니다. 이때 각각의 opr을 생각해보면

dfs(7,2) : opr => 0 0 1 0

dfs(12,2) : opr => 1 0 0 0

요걸 생각해본다면 왜 마지막에 opr의 값을 다시 +1을 해주는지 이해하시게 될 겁니다. 만약 해주지 않는다면, dfs(12,2)에 있는 opr의 값이 => 0 0 0 0이 되어 오류가 나기 때문이죠

 

이런 식으로 쭉 진행하여 갈래로 나누어지다가, dfs의 두 번째 관문 마지막 depth까지 진행하게 된다면 dfs를 종료시키는 if문을 이해하면 끝!

---

STEP 3 DFS IF문의 이해

 언제나 그렇듯이 DFS의 FOR문을 이해한다면, IF문은 간략해집니다.

public static void dfs(int a, int depth) {
		
		if(depth == N) {
			max = Math.max(max, a);
			min = Math.min(min, a);
			return;
		}
	}

depth == N 즉, 주어진 숫자를 다사용한다면, 더 이상 FOR문에 들어갈 이유가 없어지죠. FOR문보다 앞서 IF문을 작성해 줌으로써 연산을 끝내줍니다. max변수에 Math.max(max, a) 값을 비교해줍니다. 즉 기존에 있던 max값과 새로운 인자로 들어온 a를 비교하여 더 큰 수를 max에 넣어줍니다. 반대로 min에는 min과 a를 비교하여 더 작은 수를 넣어주죠. 그렇다면, 모든 갈래의 dfs로 나뉜다고 해도 결국에는 모든 경우의 수에서 가장 큰 수와 작은 수가 max와 min에 담기게 되죠. 그 후 return으로 모든 dfs를 종료시켜준다면, 다시 main 함수에서 max와 min을 println만 해주면 해당 문제는 해결되게 됩니다.

 

---

해당 문제를 풀이해보면서 아직도 dfs를 풀이함에 있어서 고려해야 하는 점을 2가지 생각해 볼 수 있었습니다.

 1. dfs에 어떠한 인자를 넣어줄 것인가

 2. dfs의 for문에 어떠한 방식으로 반복할 것인가

 

사실 2번의 경우 1번이 확실하게 정해진다면, 쉽게 작성할 수 있습니다. 결론적으로 dfs의 인자를 잘 고려해야 된다는 것을 알 수 있죠.