[SWEA] 4008번 숫자 만들기

4008번 숫자 만들기

문제 링크

 

해결방법

DFS + 백트래킹을 통해 모든 경우를 탐색하는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

• + - * / 의 경우를 모두 대입시켜 모든 연산자의 경우를 처리한다

 

문제 조건

• N ≤ 12
• 연산자 개수 = 숫자 개수 - 1
• 연산의 값은 -100,000,000 ~ 100,000,000

 

시간 복잡도

연산자의 종류는 4개이고, 개수는 최대 11개이다

따라서 연산자를 설정하는 것은 4^11 의 시간이 걸린다

또한 수식을 계산하는 과정은 최대 11 의 시간이 걸린다

따라서 O(4^11 * 11) 의 시간 복잡도를 가진다

 

 

소스코드

문제 해결 시간 : 30m

메모리 : 12632 KB

시간 : 89 ms

#include <iostream>
#include <math.h>
#include <cstring>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;

int testcase;
int n,max_ans,min_ans;
int op[4];
int num[12];

vector<int> selected;

int calc(){
    int res = num[0];
    
    for(int i=0; i<selected.size(); i++){
        switch (selected[i]) {
            case 0:
                res += num[i+1];
                break;
            case 1:
                res -= num[i+1];
                break;
            case 2:
                res *= num[i+1];
                break;
            case 3:
                res /= num[i+1];
                break;
            default:
                break;
        }
    }
    
    return res;
}

void dfs(int cnt){
    // 연산자를 모두 채웠다면
    if(cnt == n-1){
        int res = calc();
        
        min_ans = min(min_ans,res);
        max_ans = max(max_ans,res);
        return;
    }
    
    // DFS 탐색
    for(int i=0; i<4; i++){
        // 사용할 수 있는 연산자가 남았다면
        if(op[i] > 0){
            selected.push_back(i);
            op[i] -= 1;
            dfs(cnt+1);
            op[i] += 1;
            selected.pop_back();
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=1; t<=testcase; t++){
        // 입력
        cin >> n;
        for(int i=0; i<4; i++){
            cin >> op[i];
        }
        for(int i=0; i<n; i++){
            cin >> num[i];
        }
        
        min_ans = INF;
        max_ans = -INF;
        
        dfs(0);
        
        cout << "#" << t << " " << max_ans - min_ans << "\n";
    }
    
    return 0;
}