[그리디] 백준 - 30 (10610)

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

10610번: 30

 

-문제풀이

 

이런 숫자의 배수나 약수 등등처럼 수학관련된 문제는 

일단 직접 써보면서 규칙을 찾는 것이 중요하다.

 

30의 배수를 작성해보면 다음과 같다.

30 

60

90

120

150

180

210

240

270

300

...

 

규칙을 살펴보면 다음과 같다.

1. 뒤에 0이 붙는다.

2. 각 자릿수를 모두 더하면 3의 배수이다. => 3으로 나누었을 때 나머지가 모두 0

 

따라서 이 두 가지 규칙을 구현해서 문제를 풀어야 한다.

 

또한 문제의 조건은 다음과 같다.

1. 입력된 N의 숫자들로 만들 수 있는 가장 큰 30의 배수

 

 

최종적으로 문제풀이 순서는 다음과 같다.

 

1. 문자열로 입력받기

2. 입력받은 문자열 N의 길이만큼 반복하면서 N문자열을 문자로 나누면서 숫자로 만든다.

  이때 sum변수에 변환된 숫자를 모두 더해준다.

  그리고 리스트 객체에 각 숫자를 add시킨다.

3. 모든 숫자가 리스트에 add되면 리스트를 오름차순 정렬한다.

4. 30배수의 2가지 규칙을 위해 조건문을 작성한다.

  리스트의 첫 수가 0이 아니면 혹은 sum을 3으로 나눴을 때 나머지가 0이 아니면

5. 조건문이 참이면 -1출력, 거짓이면 리스트를 마지막 인덱스부터 0인덱스까지 출력시킨다.

 

 

-자바

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String N = br.readLine();
		
		//입력받은 문자열 N을 문자로 분리 후 담을 리스트
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		/*
		 * 규칙
		 * 1. 30 배수는 맨 뒷자리가 모두 0으로 끝나야 한다.
		 * 2. 30 배수의 각 자리값을 더하면 3의 배수가 되어야 한다.
		 */
		int sum = 0;
		
		int val = 0;
		for( int i=0; i<N.length(); i++ ) {
			val = N.charAt(i)-'0';
			sum += val;
			list.add( val );
		}
		
		//가장 큰 30의 배수이므로 list를 오름차순으로 정렬한다. 
		Collections.sort( list );
		
		StringBuffer sb = new StringBuffer();
		
		if( list.get(0)==0 && sum%3==0 ) {
			for( int i=list.size()-1; i>=0; i-- ) {
				sb.append( list.get(i) );
			}
			System.out.println( sb );
			
		} else {
			System.out.println( "-1" );
		}

	}

}

 

 

-파이썬

import sys

n = list(sys.stdin.readline().rstrip())
n.sort( reverse=True )

if n[-1] != '0' or sum(map(int, n)) % 3 != 0:
    print( -1 )
else:
    print( ''.join(n) )