[백준]: 10610번: 30 / 탐욕적 기법(Greedy Algorithm)

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

이 문제를 보고 간단히 생각하여 완전탐색으로 교환하여 풀었으나, 시간초과가 발생하였다. (10^5 * 10^5으로 당연히 시간초과^^)

그래서 다른 접근법을 생각해봤다. 30, 60, 120, 150, 180..

30의 배수라면

1. 마지막 수에 0이 존재해야만 한다.

2. 30의 배수라면 3의배수가 되어야만하고, 3의배수는 각자릿수의 합이 3의 배수로 나누어 떨어지면 30의 배수가 된다.

즉, 이 두가지 법칙만 적용된다면 30의 배수다. (이떄 숫자의 순서는 상관없기 떄문에 큰 순서대로 정렬해서 출력하면 된다.)

#include<iostream>

using namespace std;

#include<string>

#include<algorithm>

string s;

int Size = 0, ans = 0;

void thirty_test()

{

char test = 0;

int sum = 0;

Size = s.size();

for (int i = 0; i < Size; i++)

{

test = s[i];

sum += (int)(test-'0');

}

ans = sum;

}

int main()

{

cin.tie(0);

ios::sync_with_stdio(false);

cin >> s;

thirty_test();

sort(s.begin(), s.end());

if (s[0] == '0' && ans % 3 == 0)

{

reverse(s.begin(), s.end());

cout << s << "\n";

}

else

{

cout << "-1";

}

return 0;

}