문제 푼 날짜 : 2021-09-23

문제

문제 링크 : https://www.acmicpc.net/problem/10610

접근 및 풀이

문제를 읽자마자 무식하게 풀 수 있는 방법은 입력받은 숫자의 자릿수를 순열을 돌려서 각 케이스 마다 30으로 나눠지는지 체크하는 것이다.
하지만, 이렇게 하면 당연히 틀리게 된다. 문제의 조건을 잘 보면 아래와 같다.

N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

그러니까 자릿수가 10000개인 숫자도 입력으로 들어온다는 것이다. long long 범위도 한참 뛰어넘는 값이 들어올 수도 있다는 것인데, 순진하게 아래의 틀린코드와 같이 짜면 런타임 에러 또는 시간초과라는 결과를 보게 될 것이다.

그러면 어떻게해야 될까 고민을 해보았다. 이런 문제는 대부분 O(n)내에 끝내지 않으면 시간초과가 발생할 확률이 높아서 O(n)으로 구현하는 방법을 생각해보았다.
문제에서 굳이 30의 배수를 찾으라는 이유에 대해서 생각해보니, 30의 배수가 되려면 3의 배수이면서 10의 배수여야 한다.
3의 배수는 모든 자릿수를 더했을 때 3의 배수이면 되고, 10의 배수는 마지막 자리에 0이 붙어있으면 가능하다.
이런 아이디어를 가지고 아래와 같이 구현해주었다.

1. 주어진 숫자(실제로는 문자열로 입력받음)의 자릿수를 내림차순으로 정렬한다.
   (내림차순으로 정렬하는 이유는 0이 있는지 없는지 유무도 쉽게 확인 가능할 뿐더러 만약 30의 배수일 경우 가장 큰 수를 찾고 싶기 때문이다.)
2. 마지막 자리에 0이 있는지 확인해준다.
   2-1. 0이 없다면 어떻게든 10의 배수를 못 만들기 때문에 -1을 출력해주고 끝낸다.
   2-2. 0이 있다면 모든 자릿수를 더해줘서 3의 배수인지 확인해준다.
3. 조건에 만족하면 그 수를 출력해준다.

코드(런타임)

// 백준 10610번 : 30
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    string str = "";
    cin >> str;

    sort(str.begin(), str.end());

    long long maxNum = -1;
    do {
        long long num = stoll(str);
        if (num % 30 == 0) {
            maxNum = max(maxNum, num);
        }
    } while (next_permutation(str.begin(), str.end()));

    if (maxNum == -1) {
        cout << "-1";
    } else {
        cout << maxNum;
    }
    return 0;
}

코드

// 백준 10610번 : 30
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    string str = "";
    cin >> str;

    long long maxNum = 0;
    sort(str.begin(), str.end(), greater<>());

    if (str.back() != '0') {
        cout << -1;
    } else {
        for (char ch : str) {
            maxNum += ch - '0';
        }
        if (maxNum % 3 == 0) {
            cout << str;
        } else {
            cout << -1;
        }
    }
    
    return 0;
}

결과

피드백

깊이 생각하고 틀렸을 때 문제를 해결하는 사고력을 기르자