30 (feat. 백준, 10610번)

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

10610번: 30

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    string str;
    cin >> str;
    sort(str.begin(), str.end(), greater<>());
    if(str.back() != '0')
        cout << -1;
    else{
        register long long sum = 0;
        for(auto& ch : str)
            sum += int(ch - '0');
        if(sum % 3 == 0)
            cout << str;
        else
            cout << -1;
    }
	return 0;
}
// *&)*@*

 

반응형

1. 최초 dfs를 통해서 순열의 가장 큰 값을 구하였으나 시간 초과 판정을 받았습니다.
2. 이후 규칙을 통한 풀이를 하였으며, 해당 규칙은 다음과 같습니다.
   1. 입력받은 값의 최대값은 greater로 sort한 결과와 같다.
   2. 이때 1의 자리는 0 이어야 한다. (30으로 나눠져야 하므로)
   3. 또한 각 자릿수의 합은 3으로 나눠져야 한다. (3의 배수라면 30의 배수이기 때문. 12, 153, 99 등 3의 배수는 각 자릿수의 합도 3의 배수)