(Baekjoon) GreedyAlgorithm - (6) 30

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

10610번: 30

 

어려운문제였다. 

 

나의 접근은

1. 0이없다면 30의배수가 될수없다.

2. 내림차순으로 정리하여서 가장큰수부터 분석하면 최대한 빨리 찾을수있다.

 

하지만 틀렸다.

다음과 같은 공식을 알아야한다.

1. 0이없다면 30의 배수는 불가능하다.

2. 각자리의 숫자를 모두 더할경우 3의 배수가 되어야한다.

 

문제 자체 난이도는 매우 낮지만 모두더한것이 3의배수가 되어야한다는것은 너무 허탈했다...

혼자서 combination함수를 찾으며 최적의조건으로 풀려했던 나 자신이 불쌍했다.ㅠㅠ

다음은 내가 짠 코드다.

package GreedyAlgorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class _10610 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        
        String N = br.readLine();

        int Numcount[] = new int[10];
        Arrays.fill(Numcount, 0);   //초기화
        int numTotal = 0;   //각자리수를 더한숫자

        for (int i = 0; i < N.length(); i++) {
           Numcount[N.charAt(i) - '0']++;                               // 각자리수를 카운터하기
           numTotal += Integer.valueOf(N.charAt(i) - '0');            // 각자리를 더한숫자 
        }
        
           
        if( Numcount[0] == 0 || numTotal % 3 != 0 ){                // 숫자 0이없다면 불가능 , 모두더한값이 3으로 나눠떨어지지않으면 불가능
            System.out.println("-1");
        }
        else{
            for (int i = 9; i >= 0; i--) {                          // 내림차순으로 쓰기
                while(Numcount[i] != 0){
                    System.out.print(i);
                    Numcount[i]--;
                }
            }
        }
        

    }

}

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study