입력받은 수를 섞어서 30의 배수를 만들수 있으면, 그 때의 최댓값을 출력하라.
만들수 없다면 -1을 출력하라.
Solution
30의 배수가 되기위한 조건
(1) 수의 끝자리가 0으로 끝나야함.
ex> 60, 180, 210 ...
(2) 각 자리의 합이 3의 배수여야함
ex> 1980 -> 1+9+8 = 18 / 330 -> 3+3 = 6
''
가장 큰 수가 되기위해서는 각 자리를 내림차순해주고 위의 두 조건을 검사해보면 된다.
Code
정렬 및 각 자리의 검사를 위해서 초기값은 string으로 입력받고 int배열에 넣어주었다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string n;
cin >> n;
vector<int> a;
for (int i = 0; i < n.size(); i++)
a.push_back(n[i] - '0');
sort(a.begin(), a.end());
reverse(a.begin(), a.end()); //내림차순
int sum = 0;
bool state = false;
for (int i = 0; i < a.size(); i++) {
sum += a[i];
if (i == a.size() - 1) {
if (a[i] == 0) state = true;
}
}
if (!(sum % 3) && state) {
for (int i = 0; i < a.size(); i++)
cout << a[i];
}
else {
cout << -1;
}
return 0;
}
참고 : https://code.plus/course/43 , 그리디 알고리즘(연습)