1265. [S/W 문제해결 응용] 9일차 - 달란트2

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

SW Expert Academy

처음에 DFS로 풀었는데 답은 맞는데 시간초과 발생. 조금만 생각해보니 탐색하지 않아도 그리디적으로 해결가능.

숫자 10을 3그룹으로 나누어 곱셈이 가장 크려면 나눠진 3숫자의 차이가 최소여야한다.

즉 3,3,4가 되어야 함. 9같은 경우도 3,3,3으로 나눠졌을때 곱이 최대

이 점을 활용해서 나누기와 나머지를 통해 값의 차이가 최소인 그룹을 만들어 결과 도출.

 

 

#include<iostream>
#include<vector>
using namespace std;

int N, R;
int maxa;
int sum;
vector<int> vec;



int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> R;
		vec.clear();

		int div = N / R;
		int mod = N % R;

		for (int i = 0; i < R; i++)
		{
			vec.push_back(div);
		}
		
		int idx = 0;
		while (mod)
		{
			vec[idx]++;
			mod--;

			idx++;
			if (idx >= R)
			{
				idx = 0;
			}
		}

		long long result = 1;
		for (int i = 0; i < R; i++)
		{
			result *= vec[i];
		}

		cout << "#" << test_case << " " << result << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

 

DFS 코드

#include<iostream>
#include<vector>
using namespace std;

int N, R;
int maxa;
int sum;
vector<int> vec;


void DFS(int cur)
{
	if (cur == R - 1)
	{

		int result = 1;
		int x = 0;
		for (int i = 0; i < vec.size(); i++)
		{
			result *= vec[i];
			x += vec[i];
		}
		
		result *= (N - x);


		if (maxa < result)
		{
			maxa = result;
		}

		return;
	}

	for (int i = 1; i <= N; i++)
	{
		vec.push_back(i);
		sum += i;

		if (sum < N)
		{
			DFS(cur + 1);
		}
		
		sum -= i;
		vec.pop_back();
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> R;

		maxa = 0;
		vec.clear();
		sum = 0;

		for (int i = 1; i <= N; i++)
		{
			vec.push_back(i);
			sum += i;
			DFS(1);
			sum -= i;
			vec.pop_back();
		}
		

		cout << "#" << test_case << " " << maxa << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}