/* 연산자 끼워넣기. dfs 에서 필요한 파라미터가 무엇인지 명확히 해야 합니다. 퇴사 문제도 이것과 동일합니다. 어떤 파라미터를 가지고 갈 것인지 명확히 해야합니다. 여기서는 min, max 값 두개로 양분할 필요는 없고, sum 으로 가져가고, 나머지 연산의 밸류들을 가지고 가면 됩니다. 그리고 숫자 인덱스를 가지고 가야합니다. */ #include <iostream> #include <algorithm> using namespace std; #define SIZE 100 int N; int numArr[SIZE]; int operArr[4]; int maxVal=-1000000000, minVal=1000000000; int sum; 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 a, int b, int c, int d, int sum, int index) {
if (a == 0 && b == 0 && c == 0 && d == 0) { maxVal = max(maxVal, sum); minVal = min(minVal, sum); } if (a > 0) { dfs(a-1, b, c, d, sum+numArr[index], index + 1); } if (b > 0) { dfs(a, b-1, c, d, sum-numArr[index], index + 1); } if (c > 0) { dfs(a, b, c-1, d, sum*numArr[index], index+1); } if (d > 0) { dfs(a, b, c, d-1, sum/numArr[index], index + 1); } } int main() { problemIn(); sum = numArr[0]; dfs(operArr[0], operArr[1], operArr[2], operArr[3], sum, 1); cout << maxVal << endl << minVal << endl; return 0; } |
완전탐색, 숫자는 그대로 있고, 연산자들이 변경되는 것, 신기하게도, 이프문을 들어가고 dfs 를 나오게 되면 다시 변수들의 값이 살아나는 것을 이용합니다. 인덱스 값도 그렇고, 섬값도 그렇고, 저장해두고, 기억해두고 싶은 값들이 여러가지 일때, dfs 를 사용합니다. 오께이. |