[백준][삼성 SW 역량 테스트][Silver 1][C++] 14888 연산자 끼워넣기

문제

백준 삼성 SW 역량 테스트 기출 문제 - 14888 연산자 끼워넣기 (Silver 1)

14888번: 연산자 끼워넣기

 

---

문제 풀이

접근 방식

숫자와 각 연산자의 개수가 주어질 때, 만들 수 있는 식의 결과의 최댓값과 최솟값을 구하는 문제이다.

이 문제는 어떤 연산자를 먼저 사용할 지 결정하여 최종적인 식의 결과를 구하는 문제이기 때문에,

DFS 함수를 만들어 답을 구해주었다.

 

DFS 함수는 연산자의 개수를 저장한 벡터와, 현재 인덱스, 현재까지의 식의 결과를 매개변수로 갖도록 하였고,

for문과 switch문을 활용하여 연산자에 맞는 결괏값을 재귀적으로 호출할 DFS의 매개변수로 넘겨주도록 하였다.

모든 연산자를 다 사용했을 때에는, 그 결괏값을 MIN과 MAX와 비교하여 최솟값과 최댓값을 구해주었다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
using namespace std;

int N;
int MAX = -1000000000;
int MIN = 1000000000;
vector<int> num;

void DFS(vector<int> operator_count, int now, int result) {
	if (now == N - 1) {
		if (result > MAX)
			MAX = result;
		if (result < MIN)
			MIN = result;
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (operator_count[i] > 0) {
			operator_count[i]--;
			switch (i) {
			case 0:
				DFS(operator_count, now + 1, result + num[now + 1]);
				break;
			case 1:
				DFS(operator_count, now + 1, result - num[now + 1]);
				break;
			case 2:
				DFS(operator_count, now + 1, result * num[now + 1]);
				break;
			case 3:
				DFS(operator_count, now + 1, result / num[now + 1]);
				break;
			}
			operator_count[i]++;
		}
	}
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		num.push_back(a);
	}

	vector<int> operator_count;
	for (int i = 0; i < 4; i++) {
		int a;
		cin >> a;
		operator_count.push_back(a);
	}
	DFS(operator_count, 0, num[0]);
	cout << MAX << '\n' << MIN;
}

실행 결과

실행 결과 : 통과 (0ms)