백준(BOJ) 10610 30 *

이게 왜 그리디 알고리즘에 들어가 있는지는 모르겠다.
그리디 알고리즘 보다는 수학적 개념이 필요할 것 같다.

"모든 수들의 합이 3으로 나눠지면 3의 배수이다."

10만 자리의 숫자라는 점을 주의하자~
즉, 입력을 숫자로 받는 멍충이는 되지말자~

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>
#include <set>
#include <utility>
#include <functional>
#define MAX 40005
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;

int sum = 0, len;
char str[100005];
bool tf;
priority_queue<int> pq;

int main()
{
	scanf("%s", str);
	len = strlen(str);
	for (int i = 0; i < len; i++)
	{
		sum += str[i] - '0';
		if (!tf&&str[i] == '0')
			tf = true;
		pq.push(str[i] - '0');
	}
	if (sum % 3 == 0 && tf)
	// 0이 하나라도 있고 나머지 숫자들의 합이 3으로 나누어 떨어지면
	// 30으로 나눠진다.
	{
		while (!pq.empty())
		{
			printf("%d", pq.top());
			pq.pop();
		}
	}
	else
		printf("-1");
	return 0;
}