4008. [모의 SW 역량테스트] 숫자 만들기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

SW Expert Academy

 

 

최소 값 최대 값 범위만 잘 정해주면 간단.

최대 값이 음수일 수도 있으므로 고려해야 한다.

#include<iostream>
#include<vector>

using namespace std;
int arr[4];
int N;
vector<int> vec;

long long maxa;
long long mina;


void DFS(int cur , int idx)
{
	if (idx + 1 >= vec.size())
	{
		if (maxa < cur)
		{
			maxa = cur;
		}

		if (mina > cur)
		{
			mina = cur;
		}

		return;
	}

	if (arr[0])
	{
		arr[0]--;
		DFS(cur + vec[idx + 1], idx + 1);
		arr[0]++;

	}

	if (arr[1])
	{
		arr[1]--;
		DFS(cur - vec[idx + 1], idx + 1);
		arr[1]++;
	}

	if (arr[2])
	{
		arr[2]--;
		DFS(cur * vec[idx + 1], idx + 1);
		arr[2]++;
	}

	if (arr[3])
	{
		arr[3]--;
		DFS(cur / vec[idx + 1], idx + 1);
		arr[3]++;
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		vec.clear();
		maxa = -987654321987654321;
		mina = 987654321987654321;
		for (int i = 0; i < 4; i++)
		{
			cin >> arr[i];
		}
		
		for (int i = 0; i < N; i++)
		{
			int a;
			cin >> a;
			vec.push_back(a);
		}

		
		DFS(vec[0],0);

		cout << "#" << test_case << " " << maxa - mina << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}