문제 링크
https://www.acmicpc.net/problem/10610
문제
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.
입력
N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.
출력
미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.
조건
- 시간 제한 : 1s
- 메모리 제한 : 256MB
해설
30의 배수가 되는 조건은 10의 배수 조건과 3의 배수 조건을 동시에 만족하면 된다. 1의 자리수가 0이고(10의 배수 조건), 나머지 자리의 각 숫자의 합이 3의 배수이면 된다.(3의 배수 조건) 그러한 수 중에서 가장 큰 수를 찾고자 하였으므로, 정렬된 수에서 큰 숫자부터 차례로 나열하면 된다.
풀이
자릿수가 10000자리까지 나올 수 있으므로 하나의 변수에 수를 담는 방법으로는 불가능하다. 입력을 getchar() 한 글자씩 따로 받아와서 분리해주는 방식을 선택하였다. char 형으로 받아오기 때문에, ‘0’을 빼 int형의 숫자로 만들어주었다. 숫자의 합이 3의 배수가 되는지를 판별하기 위해 sum에 각 숫자를 더해주었다.
정렬한 숫자 vector에서 0을 갖고 있는지 확인하고 (0이니 맨 앞에 있다) sum이 3의 배수인지 확인한 뒤, 조건에 맞지 않으면 -1을 출력하고, 조건에 맞으면 뒤에서부터 역순으로 숫자를 출력하여 가장 큰 수를 만들어준다.
코멘트
이제 이정도는 간단하지.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
char inputC;
int sum = 0, index;
vector<int> numbV;
while(true) {
inputC = getchar();
if(inputC == '\n') break;
numbV.push_back(inputC-'0');
sum += inputC-'0';
}
sort(numbV.begin(), numbV.end());
if(numbV.at(0) != 0 || sum%3 != 0) {
printf("-1");
return 0;
}
for(int i = numbV.size(); i > 0; i--) {
printf("%d", numbV.at(i-1));
}
return 0;
}
Uploaded by Notion2Tistory v1.1.0