백준 10610번: 30

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

1. 문제

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

2. 알고리즘

키워드 - 정수론, 그리드 알고리즘

30 이란 숫자를 분리 하면 [3, 0] 으로 분리 할 수 있다.

분리된 수의 합은 3 임으로 3의 배수이다.

숫자 [3, 0] 의 조합으로 만들 수 있는 30의 배수 중 가장 큰 수는 [30] 이다.

숫자 102를 분리 하면 [1, 0, 2] 으로 분리 된다.

분리 된 수의 합은 3 임으로 3의 배수이다.

숫자 [1, 0, 2]의 조합으로 만들 수 있는 30의 배수 중 가장 큰 수는 [210] 이다.

문제의 조건의 30의 배수임으로 가장 작은 수로 0 이 포함 되어야 한다.

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    - 4 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;
}