백준 14888 연산자 끼워넣기 C++

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

최종 풀이

• GitHub github.com/hwayeon351/BEAKJOON-Algorithms

hwayeon351/BEAKJOON-Algorithms

//
//  main.cpp
//  BJ14888
//
//  Created by Hwayeon on 2021/07/09.
//

#include <iostream>
using namespace std;

int N;
int num[100] = {0,};
//1 +, 2 -, 3 *, 4 //
int op_cnt[5] = {0,};
int op[100] = {0,};

long long max_result = -1000000000;
long long min_result = 1000000000;

void dfs(int cnt){
    if(cnt == N-1){
        int result = num[0];
        for(int i=1; i<N; i++){
            switch(op[i]){
                case 1:
                    result += num[i];
                    break;
                case 2:
                    result -= num[i];
                    break;
                case 3:
                    result *= num[i];
                    break;
                case 4:
                    result /= num[i];
                    break;
            }
        }
        if(result > max_result) max_result = result;
        if(result < min_result) min_result = result;
        return;
    }
    for(int i=1; i<=4; i++){
        if(op_cnt[i] > 0){
            op_cnt[i]--;
            op[cnt+1] = i;
            dfs(cnt+1);
            op_cnt[i]++;
            op[cnt+1] = 0;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> num[i];
    }
    for(int i=1; i<=4; i++){
        cin >> op_cnt[i];
    }
    dfs(0);
    cout << max_result << endl;
    cout << min_result << endl;
    return 0;
}

---

풀이 과정

풀이 시간  36분

N개의 수 사이사이에 연산자를 끼워넣어 연산식을 만들어 연산 결과를 구하고 최대 결과값과 최소 결과값을 갱신해나가는 방식으로 문제를 풀었다.

연산자를 끼워 넣는 경우의 수를 구하는 것이 관건인데 dfs를 통해 모든 경우를 구했다.

//
//  main.cpp
//  BJ14888
//
//  Created by Hwayeon on 2021/07/09.
//

#include <iostream>
using namespace std;

int N;
int num[100] = {0,};

//1 +, 2 -, 3 *, 4 //
int op_cnt[5] = {0,};
int op[100] = {0,};

//-10억 <= result <= 10억
long long max_result = -1000000000;
long long min_result = 1000000000;

void dfs(int cnt){
    //연산자 배정이 완료 된 경우
    if(cnt == N-1){
        //연산 결과 구하기
        int result = num[0];
        for(int i=1; i<N; i++){
            switch(op[i]){
                case 1:
                    result += num[i];
                    break;
                case 2:
                    result -= num[i];
                    break;
                case 3:
                    result *= num[i];
                    break;
                case 4:
                    result /= num[i];
                    break;
            }
        }
        //결과값이 최소이거나 최대인 경우 값 갱신 후 재귀 종료
        if(result > max_result) max_result = result;
        if(result < min_result) min_result = result;
        return;
    }
    
    //연산자 배정
    for(int i=1; i<=4; i++){
        if(op_cnt[i] > 0){
            op_cnt[i]--;
            op[cnt+1] = i;
            dfs(cnt+1);
            op_cnt[i]++;
            op[cnt+1] = 0;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> num[i];
    }
    for(int i=1; i<=4; i++){
        cin >> op_cnt[i];
    }
    dfs(0);
    cout << max_result << endl;
    cout << min_result << endl;
    return 0;
}
#시간복잡도 = O(n^3) 공간복잡도 = O(n)

---

이전 풀이

풀이 시간 41분

 

//
//  main.cpp
//  BJ14888
//
//  Created by Hwayeon on 2021/01/17.
//

#include <iostream>
using namespace std;

int N;
int num[11] = {0, };
int op[4] = {0, };
long max_anwer = -1000000000;
long min_answer = 1000000000;

void calculate(int idx, long answer){
    if(idx == N-1){
        if(answer < min_answer) min_answer = answer;
        if(answer > max_anwer) max_anwer = answer;
        return;
    }
    int n1 = num[idx];
    int n = num[idx+1];
    long ans = 0;
    for(int i=0; i<4; i++){
        if(op[i] > 0){
            switch (i) {
                case 0:
                    if(idx == 0) ans = n1 + n;
                    else ans = n + answer;
                    break;
                case 1:
                    if(idx == 0) ans = n1 - n;
                    else ans = answer - n;
                    break;
                case 2:
                    if(idx == 0) ans = n1 * n;
                    else ans = answer * n;
                    break;
                case 3:
                    if(idx == 0) ans = n1 / n;
                    else ans = answer / n;
                    break;

            }
            op[i]--;
            calculate(idx+1, ans);
            op[i]++;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> num[i];
    }
    for(int i=0; i<4; i++){
        cin >> op[i];
    }
    calculate(0, 0);
    cout << max_anwer << endl << min_answer << endl;
    
    return 0;
}

1. max_answer, min_answer 변수 선언 및 초기화

long max_anwer = -1000000000;
long min_answer = 1000000000;

 먼저, 문제에서 결과값은 -1,000,000,000보다 크거나 같고, 1,000,000,000보다 작거나 같다고 했기 때문에, long 타입으로 선언하고 초기화 해준다.

 

 

2. Calculate() DFS

 나는 주어진 연산자를 끼워넣어 만들 수 있는 모든 경우의 수를 고려하기 위해서 DFS를 활용했다.

void calculate(int idx, long answer){
    if(idx == N-1){
        if(answer < min_answer) min_answer = answer;
        if(answer > max_anwer) max_anwer = answer;
        return;
    }
    int n1 = num[idx];
    int n = num[idx+1];
    long ans = 0;
    for(int i=0; i<4; i++){
        if(op[i] > 0){
            switch (i) {
                case 0:
                    if(idx == 0) ans = n1 + n;
                    else ans = n + answer;
                    break;
                case 1:
                    if(idx == 0) ans = n1 - n;
                    else ans = answer - n;
                    break;
                case 2:
                    if(idx == 0) ans = n1 * n;
                    else ans = answer * n;
                    break;
                case 3:
                    if(idx == 0) ans = n1 / n;
                    else ans = answer / n;
                    break;

            }
            op[i]--;
            calculate(idx+1, ans);
            op[i]++;
        }
    }
}

매개 변수로 입력에서 받아온 수열 num을 가리키는 인덱스 idx와 연산 과정 중 발생하는 계산값인 answer을 사용했다.

1. idx == N-1 인 경우, 하나의 연산식이 계산되었음을 의미한다. 계산 결과인 answer를 초기에 전역변수로 선언한 min_answer와 max_answer와 비교하여 최댓값과 최솟값을 재설정 해주고 함수를 종료한다.
2. idx == N-1이 아닌 경우, n과 n1에 num[idx], num[idx+1]을 담아준다. 처음 연산이 시작될 때(idx == 0일 때)는 n과 n1의 연산이 이루어져야하고, 첫 연산이 아닌 경우(idx > 0일 때)에는 anwer과 n의 연산이 이루어진다.
3. 반복문을 통해 입력에서 받아온 연산자의 개수를 담은 op를 탐색하여 op[i] > 0일 때(해당 연산자가 존재하는 경우), 연산자의 종류에 맞춰 연산을 진행한다. 이때, idx == 0인 경우, n과 n1의 연산을, idx != 0인 경우, n과 answer의 연산을 하여 결과값을 ans에 저장한다.
4. 연산자를 사용했으므로 op[i]--를 해주고, 재귀 함수 calculate(idx+1, ans)를 호출하여 다음 연산이 이어지도록 한다. 그 다음, 모든 경우의 수를 뽑아내기 위해 다시 op[i]++를 하여 백트래킹 해준다.

 

---

참고

• 2021/01/11 - [C++] - [알고리즘] BFS와 DFS

[알고리즘] BFS와 DFS