티스토리 뷰
1. 문제 링크
https://www.acmicpc.net/problem/10610
10610번: 30
문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는
www.acmicpc.net
2. 문제 개요
주어진 수를 적절히 재 배치하여 30의 배수중 가장 큰 수로 만들기.
3. 문제 힌트!!
3의 배수는 각 자릿수의 합이 3의 배수다.
'0'은 적어도 1개 이상 있어야 한다.
각 자릿수의 합이 3의 배수가 아닌 것은 어떻게 재 배열하여도 3의 배수가 되지 않는다.
숫자가 10^5가 아니고 10^5개 인 것을 주의하기
4. 문제 풀기
(3) 번의 조건을 다 구현하면 됩니다.
checksum은 각 자릿수가 3의 배수가 되는지 체크하기.
zero변수는 0이 1개 이상 있는지 체크하기.
조건을 다 만족한다고 했을 때, 가장 큰 숫자부터 써주는 것이 가장 큰 수가 되므로 역순으로 써주었음.
5. 코드
#include <iostream> #include <string> using namespace std; int num[10]; // 0 ~ 9 string input_string; int main() { cin >> input_string; int len = input_string.length(); int checksum = 0; bool istherezero = false; for (int i = 0; i < len; i++) { int val = input_string[i] - '0'; if (val == 0) istherezero = true; num[val]++; checksum += val; } if (checksum % 3 == 0) if (!istherezero) cout << -1; else for (int i = 9; i >= 0; --i) for (int j = 0; j < num[i]; ++j) cout << i; else cout << -1; return 0; }
지적, 댓글 언제나 환영입니다~
'알고리즘 > Greedy' 카테고리의 다른 글
| boj, 백준) 1135. 뉴스전하기 (C/C++) (0) | 2021.05.27 |
|---|---|
| boj, 백준) 3109 빵집 ( C++) (0) | 2020.02.28 |
| boj, 백준) 2812 크게만들기( C, C++ ) (2) | 2020.02.28 |
| boj, 백준) 1138 한줄로서기 (C++) (0) | 2020.02.14 |
| boj,백준 ) 2875 대회or인턴 ( C/ C++) (0) | 2020.01.24 |
댓글