SWEA 4008 숫자만들기

SWEA4008_숫자만들기

풀이

알고리즘 : BruteForce

처음엔 주어진 연산기호들로 순열을 만들어서 모든 경우에 대해 완전탐색을 하려하였으나 그렇게 되면 O(12!)가 되어 제한시간(50개에 대해 3초)를 초과할 것이라 생각되었다.

하지만 이 문제는 각 연산(최대 11개)이 결국 4가지 중 하나이고 이는 O(4^11)로 훨씬 적은 시간으로 연산을 해낼 수 있었다. 게다가 주어진 연산 갯수에 맞춰서 연산 갯수가 초과해서 연산을 수행할 수 없다. 이를 이용해서 각 단계의 연산을 골라서 최종적으로 연산 결과를 전역변수 maxRet과 minRet와 비교해서 저장하도록 하였다.

함수

• calculate : 연산이 모두 결정되면 최종 연산결과를 리턴하는 함수

• getResult : now부터 N-2 번째 연산기호를 결정하는 함수(가지고 있는 연산기호 set의 갯수를 이용해서 가능한 경우만 구한다)

  기저조건 : now가 N-1이상이 될 시 연산 결과를 구해서 전역변수에 최댓,최솟값과 비교하여 update 한다.

코드

//! 2020.02.28
// TODO SWEA4008_숫자만들기
#include<cstdio>
using namespace std;

const int MAX = 15;
const int INF = 987654321;
int T,N;
int calIdx[MAX];
int calSet[4];              // 0 : +, 1 : -, 2 : *, 3 : /
int numbers[MAX];
int maxRet,minRet;

int calculate(){
    int ret = numbers[0];
    for(int i=1;i<N;i++){
        switch(calIdx[i-1]){
        case 0:
            ret += numbers[i];
            break;
        case 1:
            ret -= numbers[i];
            break;
        case 2:
            ret *= numbers[i];
            break;
        case 3:
            ret /= numbers[i];
            break;
        }
    }
    return ret;
}

void getResult(int now){
    if(now>=N-1){
        int tmpRet = calculate();
        if(tmpRet<minRet) minRet = tmpRet;
        if(tmpRet>maxRet) maxRet = tmpRet;
        return;
    }
    for(int i=0;i<4;i++){
        if(calSet[i]!=0){
            calSet[i]--;
            calIdx[now] = i;
            getResult(now+1);
            calSet[i]++;
        }
    }
}

int main(){
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        maxRet = -INF;
        minRet = INF;
        scanf("%d",&N);
        for(int i=0;i<4;i++) scanf("%d",&calSet[i]);
        for(int n=0;n<N;n++) scanf("%d",&numbers[n]);
        getResult(0);
        printf("#%d %d\n",t,maxRet-minRet);
    }
    return 0;
}

실수

별다른 실수없이 구현하였다.