Codeforces Round #460 (Div. 2) - B. Perfect Number

1. 문제

2. 알고리즘

키워드 - 구현

* 어설픈 해석

자릿수의 합이 정확히 10 인 경우에만 양의 정수를 완전하다고 간주합니다. 양의 정수 k가 주어지면 작업은 k 번째 가장 작은 양의 정수를 구하라.

* 문제 풀이

19 라는 숫자가 있다면 각 자리수 별로 1 + 9 는 10 이 된다. 문제에서 요구 하는 사항은 자리수에 합이 10이다.

1081 또한 1 + 8 + 1 = 10 임으로 perfect number 가 된다.

모든 10 이 되는 경우의 수를 dp 배열에 담아 미리 계산 해놓고 실제 n 이 입력되는 경우에 인덱스를 찾도록 했다. 시간복잡도는 생각하지 않고 넉넉히 계산했다. 

3. 코드

#include <iostream>
#include <algorithm> // min
#include <math.h>
using namespace std;
 
long long dp[100005] = { 0, };
 
bool check(int n) {
 
    long long sum = 0;
    while (n > 0) {
        long long cand = n % 10;
        sum += cand;
        n /= 10;
    }
 
    return sum == 10;
}
int main() {
    int k;
    cin >> k;
 
    dp[0] = 0;
    int count = 1;
    for (long long i = 19; i < 100005 * 200; i++) {
        if (check(i)) {
            dp[count] = i;
            count++;
        }
    }
 
    cout << dp[k] << endl;
    return 0;
}