문제 풀이/Baekjoon Online Judge
[Baekjoon Online Judge] 10610번: 30
hyeonic
2021. 1. 24. 21:41
10610번: 30
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한
www.acmicpc.net
요구사항
- 양수 N이 주어진다.
- 양수 N에 포함되어 있는 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만든다.
입력
N을 입력받는다. N는 최대 10의 5제곱의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.
출력
미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.
30의 배수가 되기 위해서는 각 자리수의 합이 3으로 나누어 떨어져야 하고, 적어도 하나의 0이 포함되어야 한다. 30의 곱을 확인해보면 쉽게 규칙을 찾아 낼 수 있다.
30 x 0 | 0 | 30 x 10 | 300, 3 + 0 + 0 = 3 |
30 x 1 | 30, 3 + 0 = 3 | 30 x 11 | 330, 3 + 3 + 0 = 6 |
30 x 2 | 60, 6 + 0 = 6 | 30 x 12 | 360, 3 + 6 + 0 = 9 |
30 x 3 | 90, 9 + 0 = 9 | 30 x 13 | 390, 3 + 9 + 0 = 12 |
30 x 4 | 120, 1 + 2 + 0 = 3 | 30 x 14 | 420, 4 + 2 + 0 = 6 |
30 x 5 | 150, 1 + 5 + 0 = 6 | 30 x 15 | 450, 4 + 5 + 0 = 9 |
30 x 6 | 180, 1 + 8 + 0 = 9 | 30 x 16 | 480, 4 + 8 + 0 = 12 |
30 x 7 | 210, 2 + 1 + 0 = 3 | 30 x 17 | 510, 5 + 1 + 0 = 6 |
30 x 8 | 240, 2 + 4 + 0 = 6 | 30 x 18 | 540, 5 + 4 + 0 = 9 |
30 x 9 | 270, 2 + 7 + 0 = 9 | 30 x 19 | 570, 5 + 7 + 0 = 12 |
각 자리수를 더하고, 입력 받은 숫자 list에 0이 포함되어 있으면 30의 배수라고 가정하고, 정렬하여 가장 큰 순서로 수를 만들어 준다.
만약 0을 포함하지 않거나 3으로 나누어 떨어지지 않는다면 30의 배수가 아니기 때문에 -1을 출력하여 마무리한다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Baekjoon10610 {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
String number = bufferedReader.readLine();
List<Integer> list = new ArrayList<>();
int total = 0;
for (int i = 0; i < number.length(); i++) {
total += number.charAt(i) - '0';
list.add(number.charAt(i) - '0');
}
Collections.sort(list);
if (list.contains(0) && total % 3 == 0) {
for (int i = list.size() - 1; i >= 0; i--) {
bufferedWriter.write(String.valueOf(list.get(i)));
}
} else bufferedWriter.write("-1");
bufferedWriter.flush();
bufferedReader.close();
bufferedWriter.close();
}
}
해당 문제를 조합으로 해결한다면 N은 10의 5제곱 만큼의 자리수를 가지고 있기 때문에 오랜 시간이 걸릴 것으로 예상된다. 적당한 규칙을 찾아서 풀이를 해보는 편이 낫다고 판단한다.