[C++] 백준 2777번:숫자 놀이(그리디 알고리즘)

문제링크

2777번: 숫자 놀이

문제

학교에서 공부를 하고 있던 승환이는 갑자기 숫자 하나를 보고 그 숫자의 특징에 대해 생각했다. 승환이가 본 숫자는 10이다. 10은 2*5로 나타낼 수 있고 이를 조금 더 생각해서 25라는 수의 각 자릿수를 곱하면 10이 된다는 것을 알아냈다. 이를 일반적인 문제로 바꾸면 다음과 같다. 

“양의 정수 N( 1 <= N <= 1,000,000,000 )이 있을 때 모든 자릿수의 곱이 정확히 N이 되는 가장 작은 양의 정수 X를 찾아라. ”

모든 자릿수의 곱이 20인 수들을 예를 들면, 522 보다는 225가 작고 225 보다는 45가 작다.

승환이는 자신이 만든 문제를 수업 시간 전에 칠판에 써 놓았다. 그것을 본 당신은 호기심이 생겨서 그 문제를 풀어보고 싶어한다. N이 주어졌을 때 위 조건을 만족하는 가장 작은 양의 정수 X가 몇 자리 수인지 구하여라.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 양의 정수 N이 주어진다. (1 <= N <= 1,000,000,000)

출력

각각의 Test case에 대해서 조건을 만족하는 가장 작은 X가 몇 자리 수인지 출력하라. 만약 그러한 X가 존재하지 않는다면 -1을 출력하라.

 

풀이

그리디 알고리즘을 이용하여 풀이하였다.

원래 수를 나누는 가장 큰 한자리 수를 찾아 뒤부터 붙여주면 된다.

ex)

20을 나누는 가장 큰 한자리 수는 5이고 나누면 4가 된다. 따라서 5를 뒤에 붙여준다.

4를 나누는 가장 큰 한자리 수는 4이고 나누면 1이 된다. 따라서 45가 된다.

코드

#include <iostream>
#include <string>
using namespace std;
// greedy algorithm -> find and paste the largest number that can divide origin number
int n, t;
 
int main() {
    
    cin >> t;
 
    while (t--) {
        cin >> n;
 
        string ans = "";
 
        bool possible = true;    // bigger flag
        while (n >= 10 && possible == true) {
            bool poss = false;    // small flag
            for (int i = 9; i >= 2; i--) {
                if (n % i == 0) {
                    ans.insert(ans.begin(), '0' + i);
                    n = n / i;
                    poss = true;
                    break;
                }
            }
            if (poss == false) {
                possible = false;
            }
        }
 
        if (possible == false) {
            cout << -1 << "\n";
        }
        else {
            ans.insert(ans.begin(), '0' + n);
            cout << ans.size() << '\n';
        }
    }
}