4673 셀프 넘버

예전에 어려워서 안 풀었는데 다시 마주쳤다.. d(n)에서 n을 찾기는 너무 어려워 보이고 결국 n에서 만들 수 있는 모든 d(n)들을 제거한 다음 남은 수를 출력하기로 했다.

 

조금 걱정되는 부분은 반복문을 세 번 쓴다는 거였는데 각 자리수의 합 구하는 건 얼마 안 걸려서 없다고 치면 반복문이 두번이다. 그리고 반복문 두 번은 10000까지 1초안에 돌 수 있기 때문에 괜찮을 것 같았다! (게다가 -1이면 넘어가서 만 번 보다는 적을 것이다)

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v;

    for(int i = 0; i <= 10000; i++)
        v.push_back(1);

    for(int i = 1; i <= 10000; i++){
        if(v[i] == -1)
            continue;
        int n = i;

        while(n <= 10000) {
            int sum = 0, tmp = n;

            while(tmp != 0){
                sum += tmp%10;
                tmp /= 10;
            }

            n = n + sum;
            v[n] = -1;
        }
    }
    for(int i = 1; i <= 10000; i++){
        if(v[i] != -1)
            printf("%d\n", i);
    }
}

위 사진에 적은 대로 로직을 짰다.

맞췄음! 시간 0인건 채점할 때 걸린 시간인가? 저 정도로 안 적을 것 같은데