[Algorithm]브루트포스 알고리즘#2 (백준/#2231/분배합)

문제 설명

• 목표:
  • 주어진 자연수 N에 대해 가장 작은 생성자를 찾는 프로그램을 작성한다.
• 용어 정의:
  • 분해합: 자연수 M과 M을 이루는 각 자리수의 합.즉, 분해합(M) = M + (M의 각 자리수의 합)예) 245의 분해합 = 245 + 2 + 4 + 5 = 256
  • 생성자: 분해합이 N인 자연수 M.
• 문제의 특징:
  • 생성자가 없는 경우: 해당하는 M이 없다.
  • 생성자가 여러 개인 경우: 가장 작은 생성자를 찾아야 한다.
• 입력:
  • 자연수 N (1 ≤ N ≤ 1,000,000).
• 출력:
  • 자연수 N의 가장 작은 생성자.
  • 생성자가 없으면 0을 출력.
• 제약:
  • N의 범위가 크므로, 가능한 생성자를 효율적으로 탐색해야 한다.
• 알고리즘:
  • 모든 자연수 M에 대해 분해합을 계산하는 것은 비효율적.
  • 대신, 분해합을 통해 생성자 M의 범위를 좁혀서 탐색.

해결한 코드

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
using namespace std;

int main() {
  int n, solve = 1000001;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string numberStr = to_string(i);
    vector<int> v1;
    for (size_t i = 0; i < numberStr.size(); i++) {
      int digit = numberStr[i] - '0';
      v1.push_back(digit);
    }
    int sum = accumulate(v1.begin(), v1.end(), 0);
    if (sum + i == n && sum + i < solve) {
      solve = i;
      cout << i;
    }
  }
  if(solve == 1000001) cout << 0;
  return 0;
}

해결한 방법

주어진 자연수 N에 대해 가장 작은 생성자를 찾는 문제를 해결하기 위해 다음을 수행한다:

1. 생성자 후보 탐색:

   모든 숫자 i를 0부터 N-1까지 순회하며, i가 N의 생성자인지 확인한다.

2. 분해합 계산:

   숫자 i를 이루는 각 자리수의 합(자리수 합)을 계산하고, 이를 i에 더해 분해합을 구한다.

3. 생성자 확인:

   계산한 분해합이 N과 같으면, 해당 숫자 i는 N의 생성자이다.

   생성자가 여러 개일 경우, 가장 작은 생성자를 기록한다.

4. 결과 출력:

   가장 작은 생성자를 출력하며, 생성자가 없을 경우 0을 출력한다.

개선할 부분

현재 코드는 모든 i에 대해 순회하므로 비효율적이다. 개선 방법은 다음과 같다:

1. 탐색 범위 줄이기:
   • i의 최소값을 N - (N의 최대 자리수 합)로 설정.
   • 예: N = 256일 때, 탐색 범위는 256 - 54 = 202부터 256까지.
2. 벡터 제거:
   • 자리수 합은 벡터 대신, 반복문으로 바로 계산할 수 있다.

개선된 코드

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = max(1, n - 54); i < n; i++) { // 탐색 범위 줄이기
        int sum = i, temp = i;
        while (temp > 0) { // 자리수 합 계산
            sum += temp % 10;
            temp /= 10;
        }
        if (sum == n) {
            cout << i;
            return 0;
        }
    }
    cout << 0; // 생성자가 없는 경우
    return 0;
}

https://www.acmicpc.net/problem/2231