알고리즘/C++
[C++] BAEKJOON 10610 30
ssung.k
2019. 9. 15. 20:37
https://www.acmicpc.net/problem/10610
10610번: 30
문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는
www.acmicpc.net
그리디 알고리즘을 사용하여 문제를 해결하였습니다.
30의 배수인지 확인하기 위해서 두 가지를 검사해주었습니다.
- 3의 배수이기 위해서는 각 자리 수의 합이 3의 배수
- 10의 배수이기 위해서는
0이 존재
검사해서 통과했다면 내림차순으로 정렬하여 출력해줍니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(int argc, const char * argv[]) {
string input;
cin >> input;
vector <char> numList;
int sum = 0;
bool zeroCheck = false;
for (int i=0;i<input.size();i++){
if (input[i] == '0') zeroCheck = true;
sum += input[i] - '0';
numList.push_back(input[i]);
}
if (sum % 3== 0 && zeroCheck){
sort(numList.begin(), numList.end());
reverse(numList.begin(), numList.end());
for (int i=0;i<numList.size();i++){
cout << numList[i];
}
}
else {
cout << -1 << "\n";
}
return 0;
}