백준 10610번: 30

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

1. 문제

어느날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. (그 수가 존재한다면)

2. 알고리즘

키워드 - 정수론

접근 - 30 의 배수 임으로 십의 자리 수가 하나 있어야 하며, 숫 자들의 각각의 합은 3의 약수여야 한다.

0은 하나 포함 되어 있어야 30의 배수를 찾을 수 있다. 

2931의 숫자의 조합으로 만들 수 있는 순열을 구해 보면 30의 배수가 없다.

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
using namespace std;
 
#define MAX_SIZE 100
#define INF 0x7fffffff
 
/*
* @memory  - 2268 kb
* @time    - 0 ms
*/
int main() {
 
    cin.tie(0);
    std::ios::sync_with_stdio(false);
 
    string s;
    cin >> s;
    int sum = 0;
    for (char c : s) {
        sum += c - '0';
    }
    
    sort(s.begin(), s.end());
    if (s[0] == '0' && sum % 3 == 0) {
        reverse(s.begin(), s.end());
        cout << s << '\n';
    }
    else {
        cout << "-1\n";
    }
    return 0;
}