백준 14888 - 연산자 끼워넣기 - 백트래킹 (C++)

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

14888번: 연산자 끼워넣기

학교를 개강하고 정말 오랜만에 시간이 나서 알고리즘 문제를 풀어 보았다.

쉬운 문제는 그래도 술술 푸는걸 보니, 아직 감이 완전히 죽진 않은것 같다 ㅎㅎ

 

오늘 풀어본 문제는 연산자 끼워넣기. 삼성 sw 역량테스트 문제이다.

남은 연산자의 개수가 0이 될때까지, 각각의 +-*/ 연산자를 쓸 수 있는 갯수가 남아있는지 아닌지를 검사하면서

진행하면 풀 수 있는 문제이다.

 

solution(num,a,b,c,d)라는 함수를 만들어서 재귀로 호출해가면서 풀었는데, num은 지금까지 계산한 숫자이고, a,b,c,d는 각각 + - * / 의 연산자가 남은 갯수를 의미한다.

최댓값을 -10억, 최솟값을 +10억으로 초기화 한다음에,

a+b+c+d = 0이 되었을때 , 각각 최소 최대를 업데이트 해가면서 문제를 풀면 된다.

#include <iostream>
using namespace std;
const int INF = 1000000000;
int numlist[11];
int Min = INF;
int Max = -INF;
int n;
 
void solution(int num,int a,int b,int c,int d){
    int rest = a+b+c+d;
    if(rest==0){
        Min = min(Min,num);
        Max = max(Max,num);
    }
    if(a>0)
        solution(num+numlist[n-rest],a-1,b,c,d);
    if(b>0)
        solution(num-numlist[n-rest],a,b-1,c,d);
    if(c>0)
        solution(num*numlist[n-rest],a,b,c-1,d);
    if(d>0)
        solution(num/numlist[n-rest],a,b,c,d-1);
 
}
 
int main(void){
 
    cin>>n;
    for(int i=0; i<n;i++)
        cin>>numlist[i];
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    solution(numlist[0],a,b,c,d);
    cout<<Max<<"\n"<<Min;
}