SWEA4008 [모의 SW 역량테스트] 숫자 만들기 C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE&problemTitle=모의&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA4008.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA4008
//
//  Created by Hwayeon on 2021/10/18.
//

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int N;

//0 -> +, 1 -> -, 2 -> *, 3 -> /
int op[4] = {0, };
int num[12] = {0, };
vector<int> ops;

long long max_result = -100000001;
long long min_result = 100000001;

void calculate(){
    int result = num[0];
    for(int i=1; i<N; i++){
        switch(ops[i-1]){
            // +
            case 0:
                result += num[i];
                break;
            // -
            case 1:
                result -= num[i];
                break;
            // *
            case 2:
                result *= num[i];
                break;
            // /
            case 3:
                result /= num[i];
                break;
                
        }
    }
    if(result > max_result) max_result = result;
    if(result < min_result) min_result = result;
}

void get_op_permutations(int cnt){
    if(cnt == N-1){
        calculate();
        return;
    }
    for(int i=0; i<4; i++){
        if(op[i] > 0){
            op[i]--;
            ops.push_back(i);
            get_op_permutations(cnt+1);
            ops.pop_back();
            op[i]++;
        }
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        min_result = 100000001;
        max_result = -100000001;
        
        cin >> N;
        for(int i=0; i<4; i++){
            cin >> op[i];
        }
        for(int i=0; i<N; i++){
            cin >> num[i];
        }
        
        get_op_permutations(0);
        cout << "#" << test_case << " " << abs(max_result-min_result) << endl;
    }
    return 0;
}

---

풀이 과정

풀이 시간 17분

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int N;

//op[i] -> i 연산자의 개수
//0 -> +, 1 -> -, 2 -> *, 3 -> /
int op[4] = {0, };

//숫자를 담는 배열
int num[12] = {0, };

//연산자 조합을 담는 벡터
vector<int> ops;

long long max_result = -100000001;
long long min_result = 100000001;

void calculate(){
	//결과값을 맨 처음 숫자로 초기화 한다
    int result = num[0];
    
    for(int i=1; i<N; i++){
        switch(ops[i-1]){
            // +
            case 0:
                result += num[i];
                break;
            // -
            case 1:
                result -= num[i];
                break;
            // *
            case 2:
                result *= num[i];
                break;
            // /
            case 3:
                result /= num[i];
                break;
                
        }
    }
    //최댓값과 최솟값을 갱신한다
    if(result > max_result) max_result = result;
    if(result < min_result) min_result = result;
}

void get_op_permutations(int cnt){
	//N-1개의 연산자를 모두 정한 경우, 계산한다
    if(cnt == N-1){
        calculate();
        return;
    }
    
    //연산자 뽑기
    for(int i=0; i<4; i++){
    	//연산자의 개수가 남아 있는 경우, 해당 연산자를 선택한다
        if(op[i] > 0){
            op[i]--;
            ops.push_back(i);
            get_op_permutations(cnt+1);
            ops.pop_back();
            op[i]++;
        }
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
    	//최댓값, 최솟값 초기화
        min_result = 100000001;
        max_result = -100000001;
        
        cin >> N;
        for(int i=0; i<4; i++){
            cin >> op[i];
        }
        for(int i=0; i<N; i++){
            cin >> num[i];
        }
        
        //연산자 조합의 모든 경우의 수 구하기
        get_op_permutations(0);
        cout << "#" << test_case << " " << abs(max_result-min_result) << endl;
    }
    return 0;
}
//시간복잡도 = T(4^(N-1)*(N-1)) -> O(4^N*N), 공간복잡도 = O(N)