백준] 10610 - 30(COCI 2014/2015)

시간 제한 : 1초

메모리 제한 : 32MB

입력

N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있다.

출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

소스코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void)
{
	char arr[100001];
	int cnt = 0, len, tmp, sum = 0;
	cin >> arr;
	len = strlen(arr);
	for (int i = 0; i < len; i++)
	{
		if (arr[i] == '0')
			cnt++;
		else
			sum += (int)(char)(arr[i] - '0');
	}
	if (cnt == 0)
		cout << -1;
	else
	{
		if (sum % 3 == 0)
		{
			sort(arr, arr + len);
			for (int i = len - 1; i >= 0; i--)
				cout << arr[i];
		}
		else
			cout << -1;
	}
}

Tip

그리디로 분류는 하고 있지만, 답을 출력할 때만 그리디로 처리를 하는 것이고 실질적으로는 30의 배수를 어떻게 판별할 것인지를 고민해야 한다. 10의 배수인 경우(일의 자리가 반드시 0)와 3의 배수인 경우(자리수 전체를 더하면 3의 배수)를 같이 하면 30의 배수를 구할 수 있다.