/* 0852 연산자끼워넣기 2개의의 수열이 들어오고 5, 6이 들어오고 곱하기가 있습니다. */ #include <iostream> #include <algorithm> using namespace std; #define SIZE 12 int numArr[SIZE]; int operArr[SIZE]; int N; int minVal = 2123456789; int maxVal = -2123456789; void problemIn() { cin >> N; for (int i = 0; i < N; i++) { cin >> numArr[i]; } for (int i = 0; i < 4; i++) { cin >> operArr[i]; } } void dfs(int depth, int a, int b, int c, int d, int sum) { if (a == 0 && b == 0 && c == 0 && d == 0) { minVal = min(minVal, sum); maxVal = max(maxVal, sum); return; } if (a > 0) dfs(depth + 1, a - 1, b, c, d, sum + numArr[depth+1]); if (b > 0) dfs(depth + 1, a, b - 1, c, d, sum - numArr[depth + 1]); if (c > 0) dfs(depth + 1, a, b, c - 1, d, sum * numArr[depth + 1]); if (d > 0) dfs(depth + 1, a, b, c, d - 1, sum / numArr[depth + 1]); } int main() { problemIn(); dfs(0, operArr[0], operArr[1], operArr[2], operArr[3], numArr[0]); cout << maxVal << endl << minVal << endl; return 0; } |
dfs 를 중복 가능한 순열, 중복 배제한 순열, 이렇게도 풀이가 가능합니다. 오께이. 들어갔다 나왔다 이런것을 자유롭게 가능하도록 합니다. 기능을 분리해서 짜도록 합니다. 예를 들어 어제 카드를 검사하는 것은 위에 두고, 아래에 어떠한 처리를 할 것인지를 처리하도록 합니다. 그리고 리턴문이 가장 위에 있어야 하는 강박은 없애도록 합니다. 또 우주여행 문제에서 보면, 0 -> 1 로 들어가는 경우 1 -> 0 으로 들어가는 경우를 생각해보볼 수 있고, 중복 배제 순열이지만 뎁스가 모두 찰떄까지 기다리는 것이 아니라, 위에서 검사를 진행하고, 아래에서 리턴만을 돌리도록 합니다. 검사는 바로 위에서 그리고 바로 아래에서 리턴문 그리고 그 아래에 포문안에 dfs를 넣으면 됩니다. |