[BOJ] #14888 연산자 끼워넣기

시간 제한	메모리 제한	정답 비율
2 초	512 MB	46.685 %

 

14888번: 연산자 끼워넣기

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

연산자 배열로 dfs 를 해야한다.

메모리	시간
1988 KB	0 ms

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
 
ll arr[12];  int calc[4];  int n;
ll Max = -1e9; ll Min = 1e9;
 
void dfs(int idx, ll sum, int op) {
    if (op == -1) sum = arr[idx];
    if (op == 0) sum += arr[idx];
    if (op == 1) sum -= arr[idx];
    if (op == 2) sum *= arr[idx];
    if (op == 3) {
        if (sum < 0) {
            sum = abs(sum);
            sum /= arr[idx];
            sum = -sum;
        }
        else
            sum /= arr[idx];
    }
 
    if (idx == n - 1) {
        if (Max < sum) Max = sum;
        if (Min > sum) Min = sum;
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (calc[i] != 0) {
            calc[i]--;
            dfs(idx + 1, sum, i);
            calc[i]++;
        }
    }
    return;
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    for (int i = 0; i < 4; i++)
        scanf("%d", &calc[i]);
 
    dfs(0, 0, -1);
 
    printf("%lld\n%lld", Max, Min);
 
    return 0;
}

 

또 다른 방법

메모리	시간
1116 KB	0 ms

#include <stdio.h>
typedef long long int ll;
 
int n, operation[4];
ll num[11], max = -1e9, min = 1e9;
 
void dfs(int idx, int sum)
{
    if (idx == n)
    {
        min = min < sum ? min : sum;
        max = max > sum ? max : sum;
        return;
    }
    if (operation[0])
    {
        --operation[0];
        dfs(idx + 1, sum + num[idx]);
        ++operation[0];
    }
    if (operation[1])
    {
        --operation[1];
        dfs(idx + 1, sum - num[idx]);
        ++operation[1];
    }
    if (operation[2])
    {
        --operation[2];
        dfs(idx + 1, sum * num[idx]);
        ++operation[2];
    }
    if (operation[3])
    {
        --operation[3];
        dfs(idx + 1, sum / num[idx]);
        ++operation[3];
    }
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
    }
    for (int i = 0; i < 4; i++) {
        scanf("%d", &operation[i]);
    }
 
    dfs(1, num[0]);
 
    printf("%lld\n%lld\n", max, min);
}