[BOJ][10610] 30

1. 문제 링크

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

2. 사용 알고리즘

그리디

3. 풀이

30을 소인수분해하면 2 * 3 * 10

∴ 2의 배수이면서, 3의 배수이면서, 5의 배수인 수를 만들어야 한다.

1) 2의 배수 : 끝자리가 짝수인 경우

2) 3의 배수 : 각 자리수를 더해서 3의 배수인 경우

3) 5의 배수 : 끝자리가 0 또는 5로 끝나는 경우

2의 배수이면서 5의 배수가 되기 위해서는 끝자리가 0으로 끝나야 하고, 각 자리수의 합이 3의 배수가 되어야 한다.

∴ 위의 조건을 만족하는 경우, 주어진 수를 내림차순 정렬한 값이 답이된다.

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/10610.cpp

#include <iostream>

using namespace std;

int arr[13];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string s; cin >> s;
    int len = s.length(), sum = 0;
    for(int i = 0; i < len; ++i) {
        sum += s[i] - '0';
        ++arr[s[i] - '0'];
    }
    if(arr[0] == 0 || (sum % 3 != 0)) {
        cout << -1;
    } else {
        for(int i = 9; i >= 0; --i) {
            for(int j = 0; j < arr[i]; ++j) {
                cout << i;
            }
        }
    }
    cout << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/10610.java

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

public class Main {

    static int arr[] = new int[13];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int len = s.length(), sum = 0;
        for(int i = 0; i < len; ++i) {
            sum += s.charAt(i) - '0';
            ++arr[s.charAt(i) - '0'];
        }
        StringBuilder sb = new StringBuilder();
        if(arr[0] == 0 || (sum % 3 != 0)) {
            sb.append(-1);
        } else {
            for(int i = 9; i >= 0; --i) {
                for(int j = 0; j < arr[i]; ++j) {
                    sb.append(i);
                }
            }
        }
        sb.append("\n");
        System.out.println(sb);
    }
}