10610번 30 문제를 풀어보았다.
10610 30
https://www.acmicpc.net/problem/10610
10610번: 30
문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는
www.acmicpc.net
생각보다 간단한 문제에서 시간을 낭비했다.
이 문제는 30을 존경하는 미르코가 주운 숫자들로 30의 배수 중 가장 큰 숫자를 출력하고, 만들 수 없다면 -1을 출력하는 문제이다.
간단히 내림차순으로 정렬하고 0이 한개라도 들어있으며 자릿수의 합이 3의 배수라면 그 수는 30의 배수이다.
근데 입력범위가 10^5라는 것을 10^5가 최댓값이라는 줄알고 생각하다 런타임에러와 함께 조금 시간을 낭비했다.
틀렸던 이유는 단순히 10^5까지가 아니라 10^5자릿수가 주어진다는 것이였다.
배열 크기만 바꿔주니 간단히 풀었다.
#include <stdio.h>
#include <algorithm>
int main()
{
int c=0,i,s=0;
char str[100001];
scanf("%s",str);
for(i=0; str[i]; i++) {
if(!(str[i]-48)) c++;
s+=str[i]-48;
}
std::sort(str,str+i);
if(!(s%3)*c) for(i--; i>=0; i--) printf("%c",str[i]);
else printf("-1");
return 0;
}