백준 14888 연산자 끼워넣기

1. 10분컷 문제 2. dfs 는 컴퓨터가 어떻게 돌아가는지 스스로 짜보고, 그 순서대로 돌아가도록 구현을 하면 됩니다. 3. 이번 문제는 모든 연산자를 사용해보아야 하므로, 연산자를 하나씩 교대해가면서, 그리고, 다른 연산자부터 들어가도록 순서대로 쭉쭉 내려가도록 설정 되어 있습니다. 4. dfs 의 흐름을 파악해야 합니다. 빠르게 효율적인게 아니라 완전하게 실수없이 탐색하도록 하는것이 목표입니다.

/* 1645 연산자 끼워넣기 문제 10분컷 시작합니다. */ #include <iostream> #include <algorithm> using namespace std; int minVal = 2123456789; int maxVal = -2123456789; int N; int numArr[13]; int oper[4]; void problemIn() { cin >> N; for (int i = 0; i < N; i++) { cin >> numArr[i]; } for (int i = 0; i < 4; i++) { cin >> oper[i]; } } void dfs(int depth, int a, int b, int c, int d, int sum) { if (depth == (N)) { minVal = min(minVal, sum); maxVal = max(maxVal, sum); } if (a > 0) { dfs(depth + 1, a - 1, b, c, d, sum + numArr[depth]); } if (b > 0) { dfs(depth + 1, a, b - 1, c, d, sum - numArr[depth]); } if (c > 0) { dfs(depth + 1, a, b, c - 1, d, sum*numArr[depth]); } if (d > 0) { dfs(depth + 1, a, b, c, d - 1, sum / numArr[depth]); } } void solve() { dfs(1, oper[0], oper[1], oper[2], oper[3], numArr[0]); } int main() { problemIn(); solve(); cout << maxVal << endl; cout << minVal << endl; return 0; }