백준 30456번 [바닥수](C++) -yes6686- 티스토리

백준 문제 풀이: 30456 (쿠의 바닥수)

---

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

문제 설명:

쿠는 양의 정수 P에 대해, 그 자릿수의 모든 숫자를 곱한 값을 새로운 수로 계속 바꾸면서 하나의 값으로 수렴시키는 과정을 "바닥수"라고 정의하였다. 예를 들어, 1234 → 1×2×3×4 = 24 → 2×4 = 8 이므로, 1234의 바닥수는 8이다.

쿠는 바닥수를 계산하던 중, 바닥수 N과 숫자 P의 자릿수 길이 L만 남겨두고 정작 P를 잊어버렸다. 주어진 바닥수 N과 길이 L에 해당하는 P를 하나 출력해야 한다. 조건: P는 0으로 시작하지 않으며, 가능한 경우 중 아무거나 출력하면 된다.

---

문제 해결 코드

// 30456번: 쿠의 바닥수
// 바닥수가 N이 되기 위한 길이 L의 수 P 중 하나를 구성하여 출력

#include <iostream>
using namespace std;

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

    int n, l;
    cin >> n >> l;

    // 바닥수 계산 시 모든 자리의 곱이 반복되므로,
    // 첫 (l-1)자리는 1로 채우고 마지막 자리를 n으로 만들면
    // 바닥수는 1⋅1⋅...⋅1⋅n = n이 된다.
    for (int i = 0; i < l - 1; i++) {
        cout << 1;
    }
    cout << n;
}

---

코드 설명

• 핵심 알고리즘: 바닥수 정의를 역으로 활용. 자리수의 곱이 N이 되도록 1로 채우고 마지막에 N을 붙이면 된다.
• 구현 세부사항:
  • l-1개의 자리에는 모두 1을 넣고
  • 마지막 자리에는 N을 넣음 → 곱: 1⋅1⋯⋅N = N
  • 처음에 0을 출력하지 않기 때문에 항상 유효한 양의 정수가 만들어짐
• 시간 복잡도 분석:O(L) — 길이 L만큼 반복

---

결과

바닥수가 N이 되는 길이 L짜리 양의 정수 P를 출력합니다.

예시 입력:
8 4

예시 출력:
1118

설명: 1×1×1×8 = 8 → 바닥수는 8이므로 조건 만족

답이 여러 개 존재할 수 있으므로 1118처럼 간단한 형태로 출력하는 전략을 사용했습니다. 다른 아이디어가 있다면 댓글로 공유해주세요!