백준 - 30 (10610) [C++]

 이 문제는 그리디 문제이다. 나는 배수 판정법이라는 것을 모르는 상태로 이 문제를 풀었다. 일단 30의 배수가 되려면 10의 배수가 되어야 하므로 0의 개수가 0개이면 -1을 출력했다. 그 다음 여러 숫자들을 보며 규칙성을 찾았는데, 자릿수마다의 수를 모두 더한 수가 3으로 나누어떨어지면 3의 배수가 된다는 사실을 찾았다. 그래서 반신반의한 마음으로 제출했는데 맞았다. 30의 배수 중 가장 큰 수를 출력하라고 했기 때문에 입력 스트링을 내림차순으로 정렬하면 당연히 제일 큰수가 나올 것이므로 그렇게 풀었다.

 

 

 

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

using namespace std;

int main() {
	string input;

	cin >> input;

	bool flag = false;

	for (int i = 0; i < input.size(); i++) {
		if (input[i] == '0') {
			flag = true;
			break;
		}
	}

	if (!flag) {
		cout << -1 << '\n';

		return 0;
	}

	int acc = 0;

	for (int i = 0; i < input.size(); i++) {
		acc += input[i] - '0';
	}

	if (acc % 3 == 0) {
		// possible
		sort(input.begin(), input.end(), greater<char>());

		cout << input << '\n';
	}
	else {
		// impossible
		cout << -1 << '\n';
	}

	return 0;
}