14888번 - 연산자 끼워넣기 #백트래킹

esc247·2022년 8월 9일
0

Algorithm

목록 보기
7/11




14888번 연산자 끼워넣기

주어진 수와 연산자로 가능한 모든 경우 실행한 후 최댓값,최솟값 구하는 문제다.
모든 경우 확인해야 하므로 완전탐색+
중간중간에 연산자 바꾸면서 계산하므로 되돌아 와야함
-> 백트래킹 필요

Backtracking

  • DFS와 코드가 유사하지만 이전 상태로 돌리는 코드가 추가된다.
    - 이 문제에선 연산자를 바꿔가며 계산해야 하므로 이 부분을 되돌려야 한다.
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n, maxval = -100000001, minval = 1000000001;
int arr[12];
int opers[4];

void bt(int i, int res)
{
    if (i == n)
    {
        maxval = max(res, maxval);
        minval = min(res, minval);
        return;
    }
    for (int j = 0; j < 4; j++)
    {
        if (opers[j] > 0)
        {
            opers[j]--; //연산자 사용하므로 개수 빼준다
            if (j == 0)
            {
                bt(i + 1, res + arr[i]); //매개변수 전달시 i++ 형태로 전달하면 안된다!!
            }
            else if (j == 1)
            {
                bt(i + 1, res - arr[i]);
            }
            else if (j == 2)
            {
                bt(i + 1, res * arr[i]);
            }
            else if (j == 3)
            {
                bt(i + 1, res / arr[i]);
            }
            opers[j]++;	//이전 상태로 되돌린다.
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0; i < 4; i++)
    {
        cin >> opers[i];
    }
    bt(1, arr[0]); //시작과 동시에 수 사용하므로 1을 매개변수로 넘겨준다.

    cout << maxval << '\n'
         << minval << '\n';
    return 0;
}
profile
막상 하면 모르니까 일단 하자.

0개의 댓글