[SWEA] 숫자 만들기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH

문제

알고리즘 접근 방법

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

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

풀이

#include <iostream>
#include <string.h>
#include <vector>
#include <climits>

#define endl '\n'
#define DEBUG(X) cout << X << "\n";

using namespace std;

int N; // 숫자의 개수
int arr[4]; // '+', '-', '*', '/' 순서대로 연산자 카드의 개수
vector<int> number, susik; 
int minn, maxx;


void Init(){
    number.clear();
    susik.clear();
    minn = INT_MAX;
    maxx = - INT_MAX;
}

void Input(){
   cin >> N;
   for(int i=0; i<4; i++)
    cin >> arr[i];
    int data;
    for(int i=0; i<N; i++){
        cin >> data;
        number.push_back(data);
    }
}

int Calc(){
    int result = number[0];

    for(int i=0; i<susik.size(); i++){
         // '+', '-', '*', '/' 
        if (susik[i] == 0) result += number[i+1];
        else if (susik[i] == 1) result -= number[i+1];
        else if (susik[i] == 2) result *= number[i+1];
        else if (susik[i] == 3) result /= number[i+1];
    }

    return result;
}

void Dfs(int cnt){
    if (cnt == N){ // 연산자 다 썼으면 갱신
        int result = Calc();
        minn = min(minn, result);
        maxx = max(maxx, result);
    }
    else{ 
        for(int i=0; i<4; i++){
            if(arr[i] > 0){
                susik.push_back(i);
                arr[i]--;
                Dfs(cnt+1);
                arr[i]++;
                susik.pop_back();
            }
        }
    }
}

void Solve(){
   Dfs(1);
}


int main(int argc, char** argv)
{
	int test_case;
	int T;
	
    cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		Init();
        Input();
        Solve();
        cout << "#" << test_case << " " << maxx - minn << endl;
	}
	return 0;
}

정리

우앙

💡 참고 포스팅

슈퍼마리호님 블로그