[백준] 14888 : 연산자 끼워넣기

메리 크리스마스 🎄😊

 

 

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

14888번: 연산자 끼워넣기

 

위 문제가 dfs인 이유

완전탐색이고, 숫자가 주어지고 그 숫자를 모두 더하거나, 빼거나, 곱하거나, 나누어서 최대합과 최소합을 만드는 문제이기 때문이다. (처음위치~끝위치)

(비슷한 문제로는 전에 풀었던 프로그래머스: 타겟 넘버 가 있다.)

 

처음에 dp로 생각했었으나, 위 문제는 같은 부분문제가 여러 번 반복되는 최적 부분 문제가 아니고, 각 결괏값에 대해 상태를 저장하기에는 너무 많은 경우의 수를 고려해야 하므로 적절하지 않다.

 

최댓값과 최솟값

최댓값을 구할 때는 최솟값부터 시작하고(-10억-1 또는 INT_MIN)

최솟값을 구할 때는 최댓값부터 시작한다(10억+1 또는 INT_MAX)

📌 최댓값과 최솟값은 같을 수 있다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, pNum, mNum, muNum, dNum;
int mxSum=-1e9-1, mnSum=1e9+1;
int l[104];

void makeNum(int sum, int pos, int pNum, int mNum, int muNum, int dNum){
    if(pos==n){
        if (mxSum<sum) mxSum = sum;
        if (mnSum>sum) mnSum=sum;
        return;
    }
    if(pNum>0) makeNum(sum+l[pos], pos+1, pNum-1, mNum, muNum, dNum);
    if(mNum>0) makeNum(sum-l[pos], pos+1, pNum, mNum-1, muNum, dNum);
    if(muNum>0) makeNum(sum*l[pos], pos+1, pNum, mNum, muNum-1, dNum);
    if(dNum>0) makeNum(sum/l[pos], pos+1, pNum, mNum, muNum, dNum-1);
}

int main(){
    cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
    // 1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> l[i];
    }
    cin >> pNum >> mNum >> muNum >> dNum;
    //2. dfs 수행
    makeNum(l[0], 1, pNum, mNum, muNum, dNum);
    //3. 정답 출력
    cout << mxSum << "\n" << mnSum << "\n";
}