https://www.acmicpc.net/problem/10610
10610번: 30
문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는
www.acmicpc.net
1. 문제
숫자가 주어질 때, 해당 자릿수 숫자들의 조합으로 30의 배수 중 최대값을 만들어서 출력한다. 없을 경우 -1을 출력한다.
2. 접근
30의 배수는 3의 배수 중, 끝이 0으로 끝나는 수이다. 3의 배수는 각 자릿수의 합이 3의 배수인 수이다.
https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95
배수 판정법 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 배수 판정법은 배수인지 확인하려는 수의 배수가 맞는지 간단히 확인하는 것이다. 배수인지 확인하려는 수가 클 때에는 나눗��
ko.wikipedia.org
그러면 우리는 가장 큰 30의 배수를 찾는 것이므로,
1. 각 자릿수의 합이 3의 배수이고, 0이 존재하는지를 체크한다.
2. 가장 큰 숫자를 구하는 것은 각 숫자들을 내림차순으로 정리하면 된다.
3. 소스코드
numbers = list(map(int, list(input())))
if sum(numbers) % 3 != 0 or 0 not in numbers:
print(-1)
else:
numbers = list(map(str, sorted(numbers, reverse=True)))
ans = ''.join(numbers)
print(ans)'컴퓨터공학 > 알고리즘' 카테고리의 다른 글
| [백준] 1049. 기타줄 (0) | 2020.05.09 |
|---|---|
| [백준] 1120. 문자열 (0) | 2020.05.09 |
| [백준] 2217. 로프 (0) | 2020.05.09 |
| [백준] 11399. ATM (0) | 2020.05.09 |
| DP. 동전 거스름돈과 이항계수 (0) | 2020.05.01 |