[백준] 10610 30

[백준10610]30

그리디 알고리즘에 있었던 문제.
숫자를 입력받고, 가능한 수 조합 중 30의 배수가 되는 수 중 가장 큰 수를 출력한다.
처음에는 가능한 수 조합을 모두 구하려고 했는데, 30의 배수를 찾는다는게 단서였다.
1) 마지막 수가 0이 되어야 하고
2) 나머지 수 들의 합이 3의 배수여야 한다

일단 수를 입력받아 놓고, 내림차순으로 큰 수부터 정렬한다.
마지막 수가 0이 아니면 바로 -1을 출력하고 종료.
그리고 나머지 수들의 합을 구한 다음에, 3으로 나누어 떨어지면 30의 배수이므로 출력하고 종료,
3으로 나누어 떨어지지 않으면 -1 출력 후 종료.

C++ 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

//30의 배수->30으로 나누었을 떄 0이 되는 수
// 뒤에 한개 이상의 0을 가지고 있고, 각 자리수의 합이 3의 배수
//숫자 Combination

bool cmp(const int a, const int b) { //내립차순
	return a > b;
}

int main() {

	string s;
	cin >> s;

	int sum = 0;
	int len = s.length();
	vector<int> arr;

	for (int i = 0; i < len; i++) {
		int n = s[i] - '0'; //문자->숫자
		arr.push_back(n);
	}

	sort(arr.begin(), arr.end(),cmp);

	if (arr[len - 1] != 0) {
		printf("-1");
		return 0;
	} //맨 뒤 숫자가 0이 아니면 30의 배수가 아님

	for (int i = 0; i < len-1; i++) {
		sum += arr[i];
	} //각 자리의 합이 3이면 3의 배수

	if (sum % 3 == 0) {
		for (int i = 0; i < len; i++) {
			printf("%d", arr[i]);
		}
		return 0;
	}
	else {
		printf("-1");
		return 0;
	}

	return 0;
}