C++에서 자릿수 반복 합이 N이 되는 M번째 숫자 찾기

이 문제에서는 두 개의 양수 N과 M이 주어지며, 자릿수를 반복해서 더한 최종 값이 N이 되는 M번째 숫자를 찾아야 합니다.

문제 설명: 어떤 수의 각 자릿수를 계속 더해 한 자리 숫자가 될 때까지 반복했을 때, 그 최종 합이 N과 같아지는 수들 중에서 M번째에 해당하는 숫자를 구하는 것이 목표입니다.

예시를 통해 문제를 이해해 보겠습니다.

입력: N = 4, M = 6

출력: 49

풀이 접근 방법

가장 단순한 해결 방법은 모든 숫자를 하나씩 확인하면서 자릿수의 합이 N이 되는 숫자를 차례대로 세어 나가고, M번째에 해당하는 숫자를 반환하는 것입니다.

하지만 더 효율적인 방법은 공식을 활용하는 것입니다. 자릿수의 반복 합이 N이 되는 M번째 숫자는 다음 공식으로 바로 구할 수 있습니다.

M번째 숫자 = (M - 1) × 9 + N

이 공식이 성립하는 이유는, 자릿수 반복 합이 N인 수들은 N부터 시작하여 9씩 증가하는 규칙성을 가지기 때문입니다. 예를 들어 N = 4일 경우 해당하는 수들은 4, 13, 22, 31, 40, 49, ... 순서로 나열되며, 여섯 번째 수인 49가 정답이 됩니다.

솔루션 구현 예제

예제 코드

#include <bits/stdc++.h>
using namespace std;

int main() {

    int n = 4, m = 6;
    int mNumber = (m - 1) * 9 + n;
    cout<<m<<"-th number whose repeated sum of digits of a number is "<<n<<" is "<<mNumber;
    return 0;
}

실행 결과

6-th number whose repeated sum of digits of a number is 4 is 49