[백준][C++] 10610: 30

문제 링크: https://www.acmicpc.net/problem/10610

 

문제를 대충 읽으면 틀리기 쉬운 문제입니다.

• N은 최대 10^5개의 숫자로 구성되어 있다 --> string으로 입력받아야 합니다
• 30의 배수가 되는 수 중 가장 큰 수를 만들어야 한다

3의 배수인지 확인하는 것은 다들 아시겠지만 각 자리수를 다 더해서 3의 배수가 되면 3의 배수입니다.

10의 배수는 일의 자리수가 0이면 10의 배수입니다.

따라서 30의 배수가 되려면 위 두 조건을 모두 만족해야 합니다.

 

3의 배수 조건이 자리수를 더해서 3의 배수가 되기만 하면 되니, 3의 배수가 맞으면 숫자 위치를 아무리 바꿔도 3의 배수입니다.

30의 배수중 최대값을 찾으려면 어떻게 해야 할까요? 그냥 내림차순으로 정렬하면 됩니다. 그러면 0도 맨 뒤로 가서 10의 배수 조건을 만족하면서 그 중 가장 큰 값을 구할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;


const int INF = 987654321;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	string n;
	cin >> n;

	int sum = 0;
	bool has_zero = false;
	for (auto& c : n) {
		sum += c - '0';
		if (c == '0')
			has_zero = true;
	}

	if (sum % 3 == 0 && has_zero) {
		sort(n.begin(), n.end(), greater<char>());
		cout << n << '\n';
	}
	else {
		cout << -1 << '\n';
	}

	return 0;
}