본문 바로가기
Programming/Algorithm

백준 연산자 끼워넣기

by OKOK 2018. 3. 10.

/*

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를 넣으면 됩니다.