[백준 알고리즘][DFS] 14888번 연산자 끼워넣기

문제 정의

n개의 수로 이루어진 수열과 덧셈(+), 뺄셈(-), 곱셈(x), 나눗셈(÷) 중에서 n-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14888)

문제 풀이

지금 내가 풀고 있는 문제들이 전부 삼성 sw 역량 테스트 문제집에 있는 문제들인데, 왠지 다 비슷한 방식으로 푸는 문제인 것 같다. 일단 대부분의 문제가 완전 탐색으로 풀 수 있었는데 이 문제에서도 N이 2이상 11이하이므로 완전 탐색을 하더라도 시간이 많이 소요되지않는다. 어떠한 연산자가 들어왔는지를 저장해놓은 다음, 연산자를 순서가 있는 n-1개로 나열할 수 있는 경우의 수를 구해야 한다. 여기서의 연산은 괄호가 없고 앞에서부터 뒤로 쭉 계산을 해나가는 것이므로 연산자의 순서에 따라서 만들어지는 식의 결과가 달라진다. 이전에 모든 경우를 구하기 위한 DFS를 사용해서 마찬가지로 풀어준다. 

*처음에 최소, 최대값을 10억보다 작은 값으로 잡아줘서 틀렸습니다를 받았다.

코드

void DFS(int curr)

{

int i;

int result = 0;

visited[curr] = 1;

stack.push_back(curr);

if(stack.size() == N-1)

{

result = num[0];

for(i=0; i<N-1; i++){

if(cal[stack[i]] == 0) //덧셈

{

result += num[i+1];

}

else if(cal[stack[i]]==1) //뺄셈

{

result -= num[i+1];

}

else if(cal[stack[i]]==2) //곱셈

{

result = result * num[i+1];

}

else if(cal[stack[i]]==3) //나눗셈

{

if(result < 0)

{

result = - result;

result = result/num[i+1];

result = - result;

}

else

result = result/num[i+1];

}

}

Min = min(Min, result);

Max = max(Max, result);

}

else{

for(i=0; i<N-1; i++){

if(visited[i] != 1)

DFS(i);

}

}

visited[curr] = 0;

stack.pop_back();

}