[BOJ] 연산자 끼워넣기(14888)

[백준(BOJ)] 폴짝폴짝(1326) C++

문제 : BOJ_14888번 연산자 끼워넣기

문제 설명

완전탐색, dfs

1~N까지 수 사이사이에 횟수가 정해져있는 연산자를 끼워 넣을 때, 최댓값과 최솟값을 출력하는 문제입니다.

---

Solution

이 문제는 최댓값과 최솟값을 모두 구해야 되기 때문에 연산자를 사용할 수 있는 모든 경우의 수를 확인하는 완전 탐색을 이용해야 하는데,
시간 복잡도가 초과되지 않게 제한된 가장 큰 경우의 수를 생각해보아야 합니다.

연산자의 횟수가 알맞게 정해져있지만, 가장 큰 시간 복잡도를 고려하기 위해서 연산자를 제한 없이 쓸 수 있다고 가정한다면,

수의 개수 N의 최대가 11임으로, 연산자가 들어갈 수 있는 자리가 10 자리이고, 10자 리마다 4개의 연산자가 들어갈 수 있기 때문에,

가장 큰 시간 복잡도를 생각해본다고 해도, 4^10= 1,048,576 인 100만 정도의 수임으로 재귀 함수를 이용한 완전 탐색을 어렵지 않게 해낼 수 있습니다.

---

Description

1. 1~N까지의 수 사이사이마다 모든 경우의 수를 확인하는 재귀 함수 소스를 만드는 게 이 문제의 해결법
2. void dfs(int res, int conut) 형식으로 만들어 재귀로 함수가 들어갈 때 마다 결과값과 카운트값을 체크
3. 문제에서 주어진 최댓값을 min_res로 초기화, 최솟값을 max_res로 초기화하고 시작

#include <iostream>
using namespace std;
int roof, arr[12], sub[5];
void dfs(int res, int count);
int max_res = -1000000000, min_res= 1000000000; // 문제에서 준 가장 큰 수를 min_res에, 가장 작은 수를 max_res에 미리 선언
int main(void) {
    cin >> roof;
    for (int i = 0; i < roof; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < 4; i++) {
        cin >> sub[i]; // sub배열은 1번 배열 순서부터 주어진 연산자의 갯수를 넣어준다.
    }
    dfs(arr[0], 0);
    printf("%d\n%d", max_res, min_res);
    return 0;
}
void dfs(int res, int count) {
    if (count == roof - 1) { // 1~N까지의 수 라면, 연산자의 수는 N-1임으로 roof-1
        if (res < min_res) min_res = res;
        if (res > max_res) max_res = res;
        return;
    }
    // 여기서부터 네 가지의 연산자에 대한 모든 재귀함수를 실행한다.
    if (sub[0] > 0) { // sub[i] > 0 은 연산자를 사용할 수 있는 조건
        sub[0]--;
        dfs(res + arr[count + 1], count + 1);
        sub[0]++;
    }
    if (sub[1] > 0) {
        sub[1]--;
        dfs(res - arr[count + 1], count + 1);
        sub[1]++;
    }
    if (sub[2] > 0) {
        sub[2]--;
        dfs(res * arr[count + 1], count + 1);
        sub[2]++;
    }
    if (sub[3] > 0) {
        sub[3]--;
        dfs(res / arr[count + 1], count + 1);
        sub[3]++;
    }
}