백준, BOJ, 14888번, 연산자 끼워넣기 C++ [CPP]

//첫번째 풀이 2021.06.07

//두번째 풀이 2022.02.08

//세번째 풀이 2022.06.13

얘도 모든 걸 다 뒤져봐야 하는 문제다.

다만 모든 걸 뒤질 때 어떻게 뒤지느냐가 문제다.

백트래킹, DFS를 사용했다고 보면 된다.

https://www.acmicpc.net/submit/14888/29858716

 

---

 

#맞는 풀이

#include<iostream>
#include<algorithm>
#define MAX 1000000000

using namespace std;

int N;

int num[12];

int oper[4]; // {add, sub, mul, div 순}



//최대 최소
int m = MAX;
int M = -MAX;


//백트래킹 이용같다.
//입력은 현재까지의 연산결과를 받고 사용한 연산자 개수도 입력받는다
void func(int result, int count){
    // 종료시점
    if(count == N-1){
        //연산 끝나고 최댓값, 최솟값 갱신
        if(m > result) m = result;
        if(M < result) M = result;
        return;
    }
    
    //func(1번째 숫자,0번 사용)부터 시작한다. -> 숫자는 주어졌고 연산자는 아직 쓰지 않음
        for(int i = 0; i<4; i++){
            if (oper[i] == 0) continue;
            oper[i]--;
            
            if(i == 0){
                func(result+num[count+1], count+1);
            }else if(i == 1){
                func(result-num[count+1], count+1);
            }else if(i == 2){
                func(result*num[count+1], count+1);
            }else{
                func(result/num[count+1], count+1);
            }
            
            oper[i]++;
    }
}

int main(){
    cin >> N;
    for(int i = 0; i<N; i++){
        cin >> num[i];
    }
    cin >> oper[0] >> oper[1] >> oper[2] >> oper[3];
    
    //숫자 입력과 연산자의 개수 입력받고
    
    func(num[0],0);
    
    
    
    cout << M << "\n" << m << "\n"; 
}

 

 

연산자를 고르는 방법을 백트래킹을 이용해 빠짐없이 고르고

연산자를 다 골라서 연산결과가 나올 때마다

최솟값과 최댓값을 갱신해서 풀었다.

 

핵심은 백트래킹에서 연산을 어떻게 할 것인지, 파라미터를 무엇을 받을 것인지이다.

 

---

 

#다시 풀어본 풀이

#include <bits/stdc++.h>

using namespace std;

int N;
int num[100]; //숫자 100개
//add, sub, mul, div
int oper[4]; //연산자
int ansm = INT_MAX;
int ansM = INT_MIN;



void func(int cnt, int curVal){
    if(cnt == N){
        ansm = min(ansm, curVal);
        ansM = max(ansM, curVal);
        return;
    }
    
    
    for(int i = 0; i<4; i++){
        if(oper[i] == 0) continue;
        oper[i]--;//선택
        //진행
        if(i == 0){
            func(cnt+1, curVal + num[cnt]);
        }else if(i == 1){
            func(cnt+1, curVal - num[cnt]);
        }else if(i == 2){
            func(cnt+1, curVal * num[cnt]);
        }else if(i == 3){
            func(cnt+1, curVal / num[cnt]);
        }
        oper[i]++; //복원
    }
}




int main(){
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> num[i];
    }
    for(int i = 0; i<4; i++){
        cin >> oper[i];
    }
    
    func(1,num[0]);
    
    cout << ansM << '\n';
    cout << ansm << '\n';
    

    return 0;
}

 

뭔가 더 간단해진 것 같긴하다.

여기서 어려운 점은 백트래킹함수를 만드는 것인데..

과연 값을 저장해야할까? 를 생각해봐야 한다.

 

---

 

# 세번째 풀이

역시나 비슷하게 풀었다.

진짜 이 문제 푸는 법 까먹었는데.. 똑같이 풀었네

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> vec;
int oper[4];


int maxN = INT_MIN;
int minN = INT_MAX;

void func(int cnt, int result){
    if(cnt == N){
        maxN = max(maxN, result);
        minN = min(minN, result);
        return;
    }
    for(int i = 0; i<4; i++){
        switch(i){
            case 0:
                if(oper[i] != 0){
                    oper[i]--;
                    result += vec[cnt];
                    func(cnt+1, result);
                    result -= vec[cnt];
                    oper[i]++;
                }
                break;
            case 1:
                if(oper[i] != 0){
                    oper[i]--;
                    result -= vec[cnt];
                    func(cnt+1, result);
                    result += vec[cnt];
                    oper[i]++;
                }
                break;
            case 2:
                if(oper[i] != 0){
                    oper[i]--;
                    int prev = result;
                    result *= vec[cnt];
                    func(cnt+1, result);
                    result = prev;
                    oper[i]++;
                }
                break;
            case 3:
                if(oper[i] != 0){
                    oper[i]--;
                    int prev = result;
                    result /= vec[cnt];
                    func(cnt+1, result);
                    result = prev;
                    oper[i]++;
                }
                break;
        }
    }
}

int main(){
    cin >> N;
    int first = 0;
    for(int i = 0; i<N; i++){
        
        int x;
        cin >> x;
        if(i == 0)first = x;
        vec.push_back(x);
    }
    for(int i = 0; i<4; i++){
        int y;
        cin >> y;
        oper[i] = y;
    }
    func(1,first);
    cout << maxN << '\n';
    cout << minN << '\n';
    
    
    
    return 0;
    
}