이코테, 백준 - 14888

문제

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

14888번: 연산자 끼워넣기

 

dfs를 이용해 모든 경우의 수를 다 계산해 최솟값과 최댓값을 찾아내는 문제였다. 성공 떠있길래 보니까 1년 전에 풀었던 문제였는데 푼 기억이 없고 처음 보는 문제같았다. 만약 1년쯤 뒤에 또 이 문제를 보면 처음 보는 문제같을까..?

 

문제 풀이

dfs를 이용해서 연산자 4개에 대해 모든 경우에 다 적용해주었고, 종료 조건에 도달했을 때 result 값이 min과 max가 될 때마다 업데이트 해줬다.

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <queue>

using namespace std;

int N;
int arr[12];
int oper[4]; //+ - * /
int resultMax = -1000000001;
int resultMin = 1000000001;

void dfs(int result, int index) { //현재 연산 결과, arr index

    int i;

    if (index == N) { //종료 조건
        if (resultMin > result) resultMin = result;
        if (resultMax < result) resultMax = result;
        return;
    }

    for (i = 0; i < 4; i++) { //연산자 4개에 대해 dfs 수행 //+-*/
        if (oper[i] > 0) {
            oper[i]--;
            if (i == 0) { // +
                dfs(result + arr[index], index + 1);
            }
            else if (i == 1) { // -
                dfs(result - arr[index], index + 1);
            }
            else if (i == 2) { // *
                dfs(result * arr[index], index + 1);
            }
            else { // /
                dfs(result / arr[index], index + 1);
            }
            oper[i]++;
        }        
    }

}


int main() {  
    int i, j;

    scanf("%d", &N);

    for (i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }

    for (i = 0; i < 4; i++) {
        scanf("%d", &oper[i]);
    }

    dfs(arr[0], 1);

    printf("%d\n%d", resultMax, resultMin);


    return 0;
}

/*
2 
5 6 
0 0 1 0

3 
3 4 5 
1 0 1 0

6 
1 2 3 4 5 6 
2 1 1 1

*/