[백준] 10610번 - 30

문제 >

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

 

입력 >

N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

 

출력 >

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

 

해결방법 > 

그리디(DFS) 알고리즘으로 해결이라고 하기엔 3의 배수가 가지는 규칙으로 해결했다는 말이 어울릴 것 같다

 

우선 3의 배수가 가지는 성질은 

1) 배수의 끝자리는 1 ~ 9 까지 모두 나올 수 있다. (3 * 7 = 21이므로 21, 42, 63, 84, ... , 189)

2) 각자리 수의 합은 3이다. (3(3), 9(9), 12(3), 15(6), 18(9), 21(3), ...)

 

따라서 30의 배수가 되려면 2가지 조건을 만족해야한다

1) 10의 자리수는 어떤 수가 나와도 상관없지만 1의 자리수가 0이되야한다. 즉, 입력받은 데이터 중 0이 존재해야한다.

2) 각 자리수의 합이 3이되어야한다.

 

두가지 조건을 만족하는 가장 큰 수를 구한다.

 

[JAVA]

package baekjoon;

import java.util.*;
import java.io.*;

public class BOJ_10610 {
	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		String output = new String();
		ArrayList nums = new ArrayList();
		int n = input.length();
		int sum = 0;
		
		for(int i = 0; i < n; i++) {
			int tmp = input.charAt(i) - '0';
			sum += tmp;
			nums.add(tmp);
		}
		
		Collections.sort(nums, Comparator.reverseOrder());
		
		if(sum % 3 == 0 && (int)nums.get(n-1) == 0) {
			for(int i = 0; i < n; i++) {
				bw.write(nums.get(i) + "");
			}
		}
		else
			bw.write("-1");
		bw.flush();
	}
}

 

문제링크 >

https://www.acmicpc.net/problem/10610

10610번: 30