[BaekJoon 2231][🟤2] 분해합

❓ 문제

백준 2231 - “분해합”

🎯 난이도

Bronze 🟤2

🧠 풀이

1. 내 풀이 (브루트 포스)

- 알고리즘

• Brute Force

- 설명

루프를 돌며 현재 숫자 자체와 그 숫자의 각 자릿수의 숫자를 더하는 방식으로 풀었다.

안쪽 반복문에서 현재 구현 상으로는 O(1)이지만 pow라는 비싼 연산도 있고 상수 시간으로 쳐도 꽤나 비싼 연산이라 별로 좋지는 않다고 볼 수 있다.

N 범위 내의 모든 루프를 돌며 자릿수 체크와 덧셈/뺌셈 연산을 하므로 시간 복잡도는 O(N)이라고 할 수 있다.

- 코드

내 풀이 코드

#include <iostream>

#include <cmath>


using namespace std;

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

    int iN{};
    int iResult{};
    cin >> iN;

    for(int i = 1; i < iN; ++i)
    {
        int iSum{ i };
        int iTemp{ i };

        for(int j = 6; j >= 0; --j) // 각 자릿수의 숫자를 더함
        {
            int iDivide{ iTemp / static_cast<int>(pow(10, j))};

            if(iDivide == 0)
            {
                continue;
            }

            iTemp -= iDivide * static_cast<int>(pow(10, j));
            iSum += iDivide;
        }

        if(iSum == iN)
        {
            iResult = i;
            break;
        }
    }

    cout << iResult;

    return 0;
}

---

2. 추가 풀이 (최적화된 브루트 포스)

- 알고리즘

• Brute Force

- 설명

내 생각에 가장 정석 풀이인데 생각보다 괜찮은 트릭이 몇 개 있어서 좋은 풀이라고 생각했다.

1. int 자료형을 string으로 변환하고 문자열 길이를 통해 자릿수를 구한다.
2. 각 자릿수가 9일 때 자릿수의 합이 최대이므로 iN - 9 * iDigit이 최솟값이 된다.
3. 현재 숫자에 mod 연산, 나눗셈 연산을 통해 적은 반복으로 각 자릿수 더한다.

이러한 과정을 통해 상당히 최적화를 할 수 있다.

시간 복잡도를 O((log N)²) 까지 줄였으며, 이는 거의 상수 시간으로 봐도 될 정도로 빠르다.

- 코드

추가 풀이 코드

#include <iostream>

#include <string>


using namespace std;

int DigitSum(int iInput);

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

    int iN{};
    int iResult{};
    cin >> iN;

    int iDigit{ static_cast<int>(to_string(iN).length()) }; // string으로 변환한 뒤 문자열 길이로 자릿수 구함
    int iMin{ max(1, iN - 9 * iDigit) };    // 최솟값 구하기

    for(int i = iMin; i < iN; ++i)
    {
        int iSum{ i + DigitSum(i) };

        if(iSum == iN)
        {
            iResult = i;
            break;
        }
    }

    cout << iResult;

    return 0;
}

int DigitSum(int iInput)
{
    int iSum{};

    while(iInput)   // 각 자릿수 더하기
    {
        iSum += iInput % 10;
        iInput /= 10;
    }

    return iSum;
}

---

💭 후기

어떠한 정수의 전체 자릿수의 크기를 알아내는 트릭과 각 자릿수를 최소한의 반복만으로 알아내는 방식이 흥미로웠다. 알아두면 앞으로 계속해서 쓸 것 같으니 제대로 숙지해놓자.

🔗 참고자료

• 브루트 포스 알고리즘