[백준 14888번/c++] 연산자 끼워넣기

문제

주어진 수와, 연산자를 이용하여 만든 식의 결과의 최댓값과 최솟값

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

조건

• 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다.
• 주어진 수의 순서를 바꾸면 안 된다.
• 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.
• 음수를 양수로 나눌 때는 C++14의 기준을 따른다.
  • 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.

입출력

입력

• 수의 개수 N(2 ≤ N ≤ 11)
• A1, A2, ..., AN (1 ≤ Ai ≤ 100)
• 합이 N-1인 4개의 정수
  • 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수

출력

• 최댓값
• 최솟값
• 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
  • int형은 약 21억이므로 사용 가능

 

---

어떤 유형일까?

만들어질 수 있는 식에 대해 끝까지 계산을 해보아야 하므로, dfs로 탐색하면 되지 않을까

문제에서 주어진 예를 통해 살펴보자.

수: 1, 2, 3, 4, 5, 6

연산자: +(2개), -(1개), *(1개), /(1개)

아래와 같이 계산을 통해 최솟값과 최댓값을 찾아내면 된다.

---

코드 구현

dfs를 함수를 이용하여

인자로 현재까지 식의 합과 다음으로 계산하여야 할 수의 인덱스를 넘겨주었다. 

 

dfs 함수 호출 시에

모든 수를 다 연산에 이용한 경우에는

현재까지의 연산 결과와 최솟값, 최댓값을 비교하여 

최솟값과 최댓값을 찾은 경우에 업데이트 해주었고

 

그렇지 않은 경우에는 

연산자 4개에 대하여 반복문을 돌며

해당하는 연산자가 남아있는 경우를 찾으면

해당 연산자 개수를 하나 줄여주고

현재까지의 연산 결과에 추가로 연산하여  dfs 함수를 호출한다.

여기서 이후에 해당 dfs 함수 이후에 다음 줄이 실행될 때에는 

해당 연산자의 개수를 다시 하나 증가시켜주어야 한다.

 

---

성공 코드(내 코드)

#include <iostream>
#include <vector>
using namespace std;

int N, minn=2146000000, maxx=-2146000000;
vector<int> A(12, 0);
vector<int> op(4, 0); // +, -, *, /

void dfs(int sum, int AIdx){
    if(AIdx==N){
        if(sum>maxx) maxx=sum;
        if(sum<minn) minn=sum;
    } else{
        for(int i=0; i<4; i++){
            if(op[i]>0){
                op[i]--;
                if(i==0){
                    dfs(sum+A[AIdx], AIdx+1);
                } else if(i==1){
                    dfs(sum-A[AIdx], AIdx+1);
                } else if(i==2){
                    dfs(sum*A[AIdx], AIdx+1);
                } else if(i==3){
                    dfs(sum/A[AIdx], AIdx+1);
                }
                op[i]++;
            }
        }
    }
}

int main(){
    // freopen("input.txt", "rt", stdin);
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    cin >> N;
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    for(int i=0; i<4; i++){
        cin >> op[i];
    }

    dfs(A[0], 1);
    
    cout << maxx << endl;
    cout << minn << endl;

    return 0;
}

---

후기

dfs를 사용하여 주어진 수와 연산자를 이용하여 계산하니 생각보다 문제가 빨리 풀렸다. 😃