1. 배수판정법
2. 30 의 배수인지 체크 (모든 자리수의 합이 3 의 배수 & 0이 있어야 됨)
3. greedy 한 문제여서 되면 큰 값을 출력하면 정답
4. 시간제한 조심 (정렬이 필요없다. 4ms 로 풀림)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <string.h> | |
| /** | |
| * https://www.acmicpc.net/problem/10610 | |
| * BOJ 백준온라인져지 10610 30 풀이 | |
| */ | |
| using namespace std; | |
| int main () { | |
| char stringNumber[100002]; | |
| int number[10]; | |
| int sum = 0; | |
| scanf("%s", stringNumber); | |
| int size = strlen(stringNumber); | |
| for (int i = 0; i < size; i++) { | |
| int n = stringNumber[i] - '0'; | |
| number[n]++; | |
| sum += n; | |
| } | |
| if (sum % 3 == 0 && number[0]) { | |
| for (int i = 9; i >= 0; i--) | |
| while (number[i]) { | |
| printf("%d", i); | |
| number[i]--; | |
| } | |
| } else printf("-1"); | |
| } |
문제
어느날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. (그 수가 존재한다면)
입력
N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있다.
출력
미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 백준온라인져지 10866 덱 풀이 (0) | 2018.02.22 |
|---|---|
| BOJ 백준온라인져지 1966 프린터 큐 풀이 (0) | 2018.02.20 |
| BOJ 백준온라인져지 14487 욱제는 효도쟁이야!! 풀이 (0) | 2018.02.17 |
| BOJ 백준온라인져지 5567 결혼식 풀이 (0) | 2018.02.17 |
| BOJ 백준온라인져지 1076 저항 풀이 (0) | 2018.02.17 |