C/C++ - 백준 10610 30

/*  백준 10610 30
    https://www.acmicpc.net/problem/10610

* 문제
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를
존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가
되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

* 입력
N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

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

* 예제 입력 1
30

* 예제 출력 1
30

* 예제 입력 2
102

* 예제 출력 2
210

* 예제 입력 3
2931

* 예제 출력 3
-1

* 예제 입력 4
80875542

* 예제 출력 4
88755420

* 풀이

30 의 배수가 되려면 3 의 배수이면서 10 의 배수가 되어야 하는 점을 이용해서 조건을 확인

1. 마지막 수가 0 ==> 10 의 배수
2. 각 자리수들을 더한 값이 3 으로 나누어 떨어짐 ==> 3 의 배수

이 문제의 포인트는 사실

1. 주어진 숫자의 각 자리수를 이용해서 30 의 배수를 만들 수 있느냐? 를 판단
   ==> 판단은 위의 방법을 사용
2. 있다면 그냥 최대값을 만들면 된다. ==> 자리수를 descending order 로 sort

이 2 가지를 이용하면 쉽게 풀 수 있다.

*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);

    // 최대 10^5 개의 숫자로 이루어 지므로 string 으로 입력
	std::string n;
	std::cin >> n;

    // 각 자리수를 descending order 로 sort
	std::sort(n.begin(), n.end(), std::greater<>());

    // 끝 자리가 0 이 아니면 일단 30 의 배수가 될 수 없으므로 종료
    if (n[n.length() - 1] != '0') {
		std::cout << -1 << '\n';
		return 0;
	}

    // 각 자리수의 합을 구함
	long long sum = 0;
    for (const auto ch : n)
		sum += ch - '0';

    // 각 자리수의 합이 3 인지 판단하고 결과 출력
    if (sum % 3 == 0)
		std::cout << n << '\n';
    else
		std::cout << -1 << '\n';
}