[백준/c++] 14888번 - 연산자 끼워넣기

[ 문제 ]

 

 

 

 

[ 구현 ]

 

전형적인 브루트포스 문제이다. dfs를 이용하여 모든 경우의 수를 탐색하였다.

 

조건 중에 주어진 연산의 결과는 항상 -10억 ~ 10억이므로

각각 -1e9, 1e9로 잡고 dfs를 돌리면서 최대값, 최솟값을 갱신해주는 식으로 진행하였다.

 

dfs(int a, int b, int c, int d, int idx, int sum)의 형식으로 파라미터를 뒀다.

a,b,c,d는 각각 남은 +,-,*,/ 연산자들의 숫자를 의미한다.

 

dfs를 돌때마다 각각 a,b,c,d가 0이상인지 체크하고, 해당 연산자를 사용하였다는 의미로 -1을 반영하여 다음 dfs 파라미터로 넘겨주었다.

 

해당 dfs내에서 사용할 연산자가 정해지는 순간에 arr[idx]를 더할지 뺄지 곱할지 나눌지 또한 결정되므로

sum에 이를 반영한 값을 다음 파라미터 값으로 전달하였다.

 

 

사실 dfs에 대한 어느정도 이해만 있으면 굳이 설명하지 않아도 보고 이해가 갈 것이다.

 

 

 

 

[ 코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int arr[11];
int a, b, c, d;
int ans1 = -1e9;
int ans2 = 1e9;

void dfs(int a,int b, int c, int d,int idx, int sum) {
	if (idx == n) {
		ans1 = max(ans1, sum);
		ans2 = min(ans2, sum);
		return;
	}
	
	if (a > 0) {
		dfs(a - 1, b, c, d, idx + 1, sum + arr[idx]);
	}

	if (b > 0) {
		dfs(a, b - 1, c, d, idx + 1, sum - arr[idx]);
	}

	if (c > 0) {
		dfs(a, b, c - 1, d, idx + 1, sum * arr[idx]);
	}

	if (d > 0) {
		dfs(a, b, c, d - 1, idx + 1, sum / arr[idx]);
	}
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	cin >> a >> b >> c >> d;

	dfs(a, b, c, d, 1, arr[0]);

	cout << ans1 << '\n' << ans2;

	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

단계별로 풀어보기에서 백트래킹 문제로 나와있길래 풀어봤는데

굳이 백트래킹을 꼭 사용하지는 않아도 되는 듯 하다.

적은 케이스에 대해 모든 경우의 수를 체크할 때 자주 쓰이는 방식이므로 더욱 익숙해져야겠다.