[알고리즘 문제] 백준 1443번 망가진 계산기

1443번: 망가진 계산기 (acmicpc.net)

1443번: 망가진 계산기

 

문제

 1에 2에서 9 사이의 숫자를 정해진 횟수만큼 곱해 만들 수 있는 최대의 D자리 수를 만드는 문제

아이디어

 D가 최대 8자리이기 때문에 모든 경우를 구한다 해도 많은 시간이 걸리지 않습니다.

 

 1. 백트래킹을 통해 첫 번째부터 P번째 곱할 수를 모두 탐색합니다.

 2. 탐색 중 숫자가 D자리를 넘기면 해당 가지를 쳐냅니다.

 3. P번째 숫자까지 도달하면, 곱한 값을 기존 답과 비교해 더 큰 수를 골라냅니다.

 

코드

#include <iostream>
#include <cmath>
using namespace std;

int D, P;
int64_t pow_10[] = {
    1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
    100000000, 1000000000, 10000000000
};
int64_t answer = -1;

int digit(int64_t value) {
    for (int i = 1; i < 10; i++)
        if (value < pow_10[i])
            return i;
    return 10;
}

void solve(int idx, int64_t value, int prev_mul) {
    if (digit(value) > D)
        return;

    if (idx == P) {
        answer = max(answer, value);
        return;
    }

    for (int i = prev_mul; i < 10; i++)
        solve(idx + 1, value * i, i);
}

int main(void) {
    cin >> D >> P;
    solve(0, 1, 2);
    cout << answer;
}

 

기타

 숫자의 자릿수를 구하는 방법은 몇 가지가 있습니다.

// 10씩 나누기
int digit1(int value) {
    if (value >= 10)
    	return digit1(value / 10);
    return 1;
}

// log10 사용
int digit2(int value) {
	return (int)log10(value) + 1;
}

// 문자열로 변환
int digit3(int value) {
	return to_string(value).length();
}