BOJ 2777 : 숫자 놀이

• 문제 링크 : boj.kr/2777
• 난이도 : S2
• 태그 : 그리디

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        int ans = (n==1);
        for(int i = 9; i > 1; i--) {
            while(n % i == 0) {
                n /= i;
                ans++;
            }
        }
        if(n > 9) cout << "-1\n";
        else cout << ans << "\n";
    }

    return 0;
}

---

풀이

9부터 2까지 차례대로 나누어보며 나누어떨어지는 횟수만큼 count를 더한다.

가능한만큼 나누고 난 뒤의 결과물이 두자리 이상이라면 이는 불가능한 경우이다.

결과물이 1이라면 가능한 경우이므로 count를 출력한다.

단 n == 1인 예외 케이스를 조심해야 한다.