[10610] 30

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

10610번: 30

 

---

 

🔎 해결 방법

우선 30의 배수가 되기 위해서는 두 가지를 만족해야 한다.

1. 일의 자리가 0
2. 각 자리의 합이 3의 배수

따라서 코드도 이런식으로 짜면 된다.

 

---

 

✍️ 알고리즘

1. string으로 문자열을 입력받은 후, sort 함수를 사용해서 오름차순으로 정렬한다.

• ex) 입력 : 80875542 -> 정렬한 후 : 02455788

2. 문자열의 첫번째 원소가 0인지 확인

• 0이라면 30의 배수가 되기 위한 첫번째 조건을 만족한 것!
• 0이 아니라면 -1을 반환하고 종료

3. 첫번째 원소가 0이라면, 각 자리의 합이 3의 배수인지 확인

• 3의 배수라면, 주어진 문자열이 30의 배수라는 뜻이므로 만들 수 있는 가장 큰 30의 배수를 출력하면 된다.
• 이때 가장 큰 30의 배수는 그냥 오름차순으로 정렬했던 문자열을 마지막 원소부터 차례로 출력해주면 된다.
• 3의 배수가 아니라면 -1을 반환하고 종료
• ex) 02455788 -> 출력(답) : 88755420

 

알고리즘은 맞았지만 처음에 코드를 제출했을 때 틀렸다고 뜬 이유는

첫번째 원소는 0이지만 각 자리의 합이 3의 배수가 아닐 때도 -1을 출력했어야 하는데 여기를 처리해주지 않았기 때문!

 

---

 

💡 내 코드(C++)

// [10610] 30
// https://www.acmicpc.net/problem/10610
// 그리디 알고리즘, 정수론

#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
    string n;
    int sum = 0;
    cin >> n;
    sort(n.begin(), n.end());
    for(int i = 0 ; i < n.size() ; i++) {
        sum += n[i] - '0';
    }

    // 1. 일의 자리를 0으로 만들 수 있는지 확인(0이 있는지 확인)
    if(n[0] == '0') {
        // 2. 3의 배수인지 확인
        if(sum % 3 == 0) {
            for(int i = n.size() - 1 ; i >= 0 ; i--) {
                cout << n[i];
            }
        }
        else {
            cout << -1 << endl;
        }
    }
    else {
        cout << -1 << endl;
    }
}