[알고리즘] 백준 10610번: 30 (C++), 3의 배수

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

10610번: 30

30의 배수가 되는 경우를 백트래킹을 돌려야 하나 생각했는데 수의 길이가 10^5만큼 주어져서 시간 초과가 날 거 같았다.

이 문제는 수학적인 접근이 필요하다.

우선 30의 배수가 될 수 있는 조건은

• 0이 포함되어야 한다. (끝자리에)
• 모든 수를 더했을 때, 3의 배수여야 한다.

3의 배수 조건 == (각 자리의 수를 더했을 때, 3의 배수여야 한다.)

다음 수학 지식을 가지고 있다면 풀 수 있었다.

그리고, 출력할 때는 가장 큰 수이기 때문에 가장 큰 수부터 출력한다.

0은 자동으로 맨 마지막에 출력된다.

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

bool cmp(char a, char b) {
	return a > b;
}

int main() {
	cin >> v;
	bool zeroExist = 0;
	int sum = 0;
	for (int i = 0; i < v.size(); i++) {
		char temp = v[i];
		if (temp == '0') zeroExist = 1;
		sum += temp - '0';
	}

	if (sum % 3 == 0 && zeroExist) {
		sort(v.begin(), v.end(), cmp);
		for (int i = 0; i < v.size(); i++) cout << v[i];
	}
	else cout << -1;
	return 0;
}