[C++] 백준 14888. 연산자 끼워넣기

🌽 문제

🥕 입출력

🥔 풀이

dfs에 index 값과 계산되고 있는 return 값을 함께 넘겨주도록 했다.
연산자를 잠깐 빼와서 쓰다(dfs 재귀호출)가 도로 갖다놓는 것을 반복한다.
마지막 index 뒤에는 연산자가 붙을 필요가 없기 때문에
return 조건은 index와 n(사이즈) - 1이 같을 때이다.

실버1 포비아 이슈로 잠시 미뤄뒀던 문젠데 막상 풀어보니 별 거 없었다.
나 이제 dfs 아나보다

🥬 코드

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int n;
int arr[11], ops[4];
int maxi = INT_MIN;
int mini = INT_MAX;
bool flag;

void dfs(int idx, int ret) {
	if (idx == n - 1) {
		maxi = max(maxi, ret);
		mini = min(mini, ret);
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (ops[i] == 0) continue;
		ops[i] -= 1;
		if (i == 0) dfs(idx + 1, ret + arr[idx + 1]);
		else if (i == 1) dfs(idx + 1, ret - arr[idx + 1]);
		else if (i == 2) dfs(idx + 1, ret * arr[idx + 1]);
		else dfs(idx + 1, ret / arr[idx + 1]);
		ops[i] += 1;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 0; i < 4; i++) cin >> ops[i];
	dfs(0, arr[0]); 
	cout << maxi << "\n" << mini;
	return 0;
}

🥜 채점

벌써 일주일이 지나긴 했지만 새해를 맞아 멋진 이모지들을 달아줬다.
실버도 기분은 낼 수 있잖아
혼자 찔린 것이 맞다