[Baekjoon] 10610번: 30

 그리디 알고리즘을 연습하기 위해서 찾은 문제다.

 

 30의 배수

  - 3의 배수 : 모든 자릿수의 합이 3의 배수가 되면 된다.

  - 10의 배수 : 1의 자리 수가 0이면 된다.

 위의 조건을 만족하는 상황에서 가장 큰 수를 만들면 된다. 가장 큰 수는 주어진 수들을 내림차순 정렬함으로써 얻을 수 있다.

Ex. 2931 -> 9321

 코드는 3의 배수인지를 확인하고 내림차순 정렬한 후 끝자리가 0인지를 확인하는 것으로 끝난다.

// https://www.acmicpc.net/problem/10610
// [2017-06-26] 14시 05분
 
#include <iostream>
#include <stdlib.h>
#include <cstring>
 
using namespace std;
 
bool check(char buff[], size_t len) {
    unsigned int total = 0;
 
    for (int i = 0; i < len; i++)
        total += buff[i] - '0';
 
    if (total % 3 == 0)    return true;
    else                return false;
}
 
int compare(const void *pCh1, const void *pCh2) {
    char ch1 = *(char *)pCh1;
    char ch2 = *(char *)pCh2;
 
    if (ch1 > ch2)            return -1;
    else if (ch1 < ch2)        return 1;
    else if (ch1 == ch2)    return 0;
}
 
int main() {
    char buff[100001];
    size_t buffLen;
 
    cin >> buff;
    buffLen = strlen(buff);
 
    if (!check(buff, buffLen))
        cout << -1 << endl;
    else {
        qsort(buff, buffLen, sizeof(char), compare);
 
        if (buff[buffLen - 1] != '0')
            cout << -1 << endl;
        else
            cout << buff << endl;
    }
 
    return 0;
}

 가장 큰 수를 앞자리로 가져오는 것이 그리디 알고리즘인거 같다.