알고리즘 공부/탐욕알고리즘(Greedy)

백준 10610 (30) / 배수판별법

kdhoooon 2021. 1. 17. 19:59

문제


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

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

 

 

풀이


30의 배수판별법

  •  0이 있는지 확인
  •  0이 아닌 나머지숫자를 가지고 3의 배수를 만들수 있는지 확인하면 된다.

 

 

3의 배수 판별법

  • 전체 자리수의 숫자합이 3의 배수 여야한다.

다른 배수 판별법을 보고싶으면 밑에 링크에서 확인할 수 있다.

bhsmath.tistory.com/149

 

[보충] 배수 판별법

이 페이지는 어떤 수가 2의 배수, 3의 배수, 4의 배수, 9의 배수, 11의 배수가 되는 지를 확인 하는 방법에 대한 페이지입니다.    어떤 수가 2의 배수인지 3의 배수인지 등등을 확인하는 방법에 대

bhsmath.tistory.com

 

 

 

이렇게 찾아진 숫자가 30의 배수라면 있는 숫자들을 내림차순로 정렬하면 가장 큰 수가 나온다.

 

하지만 문제는 입력에서 105자리수의 숫자를 입력한다. Integer 와 Long 모두 이를 담을 수 없기에 String 을 가지고 해야한다.

 

 

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		String n = br.readLine();
		int check = 0;
		int i = 0;
		List<Integer> num = new ArrayList<Integer>();
		while( i < n.length()) {
			check += Integer.parseInt(n.substring(i, i+1));
			num.add(Integer.parseInt(n.substring(i, i+1)));
			i++;
		}
		
		Collections.sort(num, Comparator.reverseOrder());
		if(check % 3 == 0 && num.get(num.size()-1) == 0) {
			for(int j : num) {
				sb.append(j);
			}
		}
		else {
			sb.append(-1);
		}

		
		System.out.println(sb);
	}
}

'알고리즘 공부 > 탐욕알고리즘(Greedy)' 카테고리의 다른 글

백준 2873 (롤러코스터)  (0) 2021.01.21
백준 1931(회의실 배정)  (0) 2021.01.19
백준 1783(병든 나이트)  (0) 2021.01.18
백준 2875 ( 대회 or 인턴)  (0) 2021.01.17
백준 11047(동전 0)  (0) 2021.01.17