백준 10610 : 30

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

1. 접근

• 우선 30의 배수가 갖는 특징을 파악해보았다. 30의 배수이기 때문에 무조건 0을 하나는 가지고 있어야 한다.
• 마지막에 수를 출력하게하는데, 이 문제에서 N은 10^5까지나 되는 개수의 숫자를 가지고 있는다. => 즉, '숫자' 형태로 출력하지 않게 할 것이다. => 숫자를 문자로만 처리해야 한다.
• 그렇다면, 직접 수를 만들어서 30의 배수인지 확인하지 않고, 30의 배수인지 알기 위해, 각 자리수로만 접근해본다.
• => 3의 배수는 모든 자리의 수의 합이 3의 배수가 나와야 한다.
• 즉, 숫자를 섞어 30의 배수가 나오려면, 0을 하나 반드시 가지면서 수들의 합이 3의 배수여야 한다!
• 이 숫자가 30의 배수를 만들 수 있는지 파악했다면, 그 숫자가 어떤 숫자인지 알아내야 한다.
• 가장 큰 30의 배수를 출력하라고 했고, 가장 큰 수는 앞에서부터 가장 큰 수가 나와주면 된다.
  => 숫자를 내림차순 정렬하면 가장 큰 수가 된다.

2. 나의 풀이

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 100001
using namespace std;

bool cmp(char x, char y) { //내림차순 함수
	return (x > y);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	char n[MAX];
	cin >> n;

	int IsContainsZero=false;
	int sum = 0;
	for (int i = 0; i < strlen(n); i++) { //각 숫자의 합을 구한다. 0이 있으면 표시한다.
		sum +=n[i]-'0';
		if (n[i] == '0')	IsContainsZero=true;
	}

	if (IsContainsZero && (sum % 3) == 0) {
		sort(n, n+strlen(n),cmp); //숫자를 내림차순 정렬한다.
		cout << n << "\n";
	}
	else cout << "-1\n";

	return 0;
}