[코딩테스트 20일차] BAEKJOON 2231번 : 분해합

[BAEKJOON 2231번 : 분해합]

[문제]

---

[고찰]

해당 문제를 어떻게 효율적으로 풀지에만 정신이 팔렸고, 그러다보니 문제의 알고리즘에 접근조차 못했던 것 같습니다.

 

3자리의 숫자라면 for문을 세 번 돌려, 각각의 초기식 변수 i, j, k에 대해 101 x i + 11 x j + 2 x k == N으로 풀 수 있었을 것입니다.

하지만, 자릿수는 정해지지 않았기에 해당 방법으로는 풀 수 없습니다.

 

그 뒤로는 N을 string 객체로 입력 받은 뒤, n.size() - 1을 i로 설정하여 (10^i + 1) x m, 뭐 이런 식으로도 풀어보려고 했습니다만, 정답으로 연결짓지 못하는 잘못된 방법이었습니다.

 

해당 문제는 '브루트포스(Brute Force)' 알고리즘을 사용하면 되는데, 브루트포스 알고리즘은 가능한 모든 경우의 수를 무작정 다 시도해보는 방식의 알고리즘입니다.

 

문제에서 분명히 가장 작은 생성자를 구하라고 하였기에 쉽게 1부터 시작하여 N - 1까지 올라가면서 M의 각 자리의 숫자 합과 M의 합을 구하여서 N과 같은지를 확인하면 됐던 문제였습니다.

---

[개념]

가능한 모든 후보 생성자 i를 1부터 N - 1까지 다 시도해봅니다.

i를 currentNum 변수에 저장한 뒤, digitSum 변수에는 currentNum % 10으로 각 자릿수의 합을 더해줍니다. 이와 동시에 currentNum을 10으로 나눈 몫을 다시 currentNum에 저장해줍니다.

 

이 후 i와 digitSum의 합이 N인지를 확인하면 됩니다.

---

[정리]

문제를 푼 뒤 봤을 때는 생각보다 어렵지 않지만, 어떻게 효율적으로만 풀지에 정신이 팔려서 전체적인 흐름을 놓쳤던 것 같습니다.

완전 탐색(브루트포스)을 하는 것이 가장 효율적인 걸수도 있는데, 그러지 못했던 걸 생각하면 반성이 됩니다.

좀 더 많은 문제를 풀면서 더 넓은 시야를 가져야겠습니다.

---

[Solution]

#include <iostream>

using namespace std;

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

    int N;
    std::cin >> N;

    for (int i = 1; i < N; i++)
    {
        int currentNum = i;
        int digitSum = 0;

        while (currentNum > 0)
        {
            digitSum += currentNum % 10;
            currentNum /= 10;
        }

        int sum = i + digitSum;

        if (sum == N) {
            cout << i;
            return 0;
        }
    }

    cout << 0;
    
    return 0;
}