문제 링크 : https://www.acmicpc.net/problem/10610
10610번: 30
문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는
www.acmicpc.net
문제
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.
입력
N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.
출력
미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.
풀이
간단한 문제이다. 두 가지만 해결하면 되는데
첫 번째, 입력으로 주어지는 N은 10^5개의 숫자로 구성되어있다. 이는 N이 10만 단위까지가 아니라, 10^5개의 숫자이므로 문자열로 받아 처리해야한다.
두 번째, 30의 배수가 되는 가장 큰 수를 만들고자 한다. 30 = 2 x 5 x 3 이므로, 이 수는 2와 5 그리고 3의 배수의 조건을 모두 만족시켜야한다. 우선, 2와 5의 배수를 만족시키려면 단순히 N에 0이 존재하면 된다(N은 0으로 시작하지 않으므로).
이후 3의 배수만 만족시키면 되는데, 3의 배수이기위한 조건은 각 자릿수를 더해 3의 배수가 되면 3의 배수가된다
따라서 위 조건을 모두 만족시키면서, 입력받은 수들을 내림차순으로 정렬해 합치면 그 수가 가장 큰 수이다.
소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string s; cin >> s;
int sum = 0; //3의 배수인지 체크
int zero_chk = 0;
for (char i : s) {
int k = i - '0';
if (k == 0) zero_chk = 1;
sum += k;
}
sort(s.begin(), s.end());
if (zero_chk && sum % 3 == 0) {
reverse(s.begin(), s.end());
cout << s;
}
else printf("%d", -1);
return 0;
}
|
cs |
개발환경 : Visual Studio 2019
지적, 조언 언제든지 환영입니다~~