[그리디 알고리즘] 30

예제 입력 1

30

예제 출력 1

30

예제 입력 2

102

예제 출력 2

210

예제 입력 3

2931

예제 출력 3

-1

 

https://www.acmicpc.net/problem/10610

10610번: 30

- 30을 소인수분해 해보면, 5 x 3 x 2이다. 따라서, 맨 마지막 자리에는 무조건 0이 와야하며, 각 자리수의 합이 3의 배수가 되어야 한다.

- 가장 큰수를 구하라고 했으므로, 입력을 내림차순으로 정렬한 다음, 위 조건에 맞는지 판단하면 된다.

#include <stdio.h>

constexpr int MAX_COUNT = 100001;

char input[MAX_COUNT];
char tempInput[MAX_COUNT];

void mergeSort(int start, int end)
{
	if (start >= end) return;
	int mid = (start + end) / 2;

	mergeSort(start, mid);
	mergeSort(mid + 1, end);

	int i = start;
	int j = mid + 1;
	int k = 0;

	while (i <= mid && j <= end)
	{
		if (input[i] >= input[j])
		{
			tempInput[k++] = input[i];
			i++;
		}
		else
		{
			tempInput[k++] = input[j];
			j++;
		}
	}

	while (i <= mid)
	{
		tempInput[k++] = input[i];
		i++;
	}

	while (j <= end)
	{
		tempInput[k++] = input[j];
		j++;
	}

	for (int i = start; i <= end; i++)
		input[i] = tempInput[i - start];
}

int main(void)
{
	scanf("%s", input);

	int idx = 0;
	int sum = 0; 

	while (input[idx] != '\0')
	{
		sum += (input[idx] - '0');
		idx++;
	}

	mergeSort(0, idx - 1);

	if (sum % 3 == 0 && input[idx - 1] == '0')
	{
		printf("%s\n", input);
	}
	else
	{
		printf("-1\n");
	}
	

	return 0;
}