백준 2777번 [숫자 놀이](C++) -yes6686- 티스토리

백준 문제 풀이: 2777 [숫자 놀이]

---

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

문제 설명:

자연수 n이 주어졌을 때, n을 한 자리 수의 곱으로 표현하기 위해 필요한 최소의 한 자리 수 개수를 구하는 문제입니다. 만약 n을 한 자리 수들의 곱으로 나눌 수 없다면 -1을 출력합니다.

---

문제 해결 코드

// 백준 2777 - 숫자 놀이
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T; // 테스트 케이스 수

    while (T--) {
        int n;
        cin >> n;

        // n이 한 자리 수라면 곱셈 없이 바로 출력
        if (n < 10) {
            cout << 1 << '\n';
            continue;
        }

        int cnt = 0; // 필요한 숫자 개수

        while (true) {
            bool divisible = false;

            // 9부터 2까지 나눌 수 있는 가장 큰 수로 나누기
            for (int i = 9; i >= 2; i--) {
                if (n % i == 0) {
                    n /= i; // 나눈 결과로 갱신
                    cnt++;  // 숫자 개수 증가
                    divisible = true;
                    break;
                }
            }

            if (n < 10) { // n이 한 자리 수가 되면 종료
                cnt++;
                break;
            }

            if (!divisible) { // 나눌 수 없는 경우
                cnt = -1;
                break;
            }
        }

        cout << cnt << '\n'; // 결과 출력
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 큰 수부터 나누는 방식으로, 9부터 2까지 나눌 수 있는 가장 큰 수로 나눕니다.
  • 나눌 수 없을 경우 -1을 출력합니다.
• 구현 세부사항:
  • 입력 값 n이 한 자리 수라면 바로 1을 출력합니다.
  • 반복적으로 n을 나누며 필요한 숫자 개수를 카운트합니다.
  • 나눌 수 없는 경우를 확인하기 위해 divisible 변수를 사용합니다.
• 시간 복잡도 분석:
  • 나눗셈 반복 횟수는 약 log(n)에 비례합니다.
  • 테스트 케이스가 T개일 때, 총 시간 복잡도는 O(T ⋅ log(n))입니다.

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!