[BOJ 4673] 셀프 넘버

1) 문제 링크

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

2) 접근

맨 처음엔 1을 생성자로 해서 10000 이하인 항들까지 쭉 출력하는 아주 쉬운 문제로 생각했다. 근데 아니었쥬?
그 다음으로 접근한 건 수학적 증명을 이용한 함수를 만드는 것. 셀프 넘버라면 반드시 만족시키는 수학적 성질이 있을 것이고 이를 이용하면 아주 짧은 시간 내에 풀 수 있을 것이라 생각했다. 일단 1자리, 2자리, 3자리, 4자리인 경우로 나눠서 시작했는데… 문자가 잔뜩 있는 부정방정식만 나와서 걍 노답이라 생각하고 일단 접어뒀다.
그 다음 생각한 건 단순 노가다. 1부터 9999까지 생성자로 수를 만들고, 크기가 10000인 체크 배열을 만들어 셀프 넘버가 아닌 걸 지워나가는 방식이다.

3) 아이디어 + 풀이

마지막에 생각한 아이디어 그대로 구현해봤다. 처음 짠 코드는 이렇다.(C++11)

#include <iostream>
using namespace std;

int check[10001];
// 셀프 넘버 아닌 수 체크
int CheckNotSelfNum(){
    int di, temp; // num 넣어서 나오는 항 값, i값 임시저장소
    // d(i) 값 계산 후 check 배열 인덱스 대입 하여 체크
    for(int i=1; i<=10000; ++i){
        di = i;
        temp = i;
        while(temp){
            di += temp%10;
            temp /= 10;
        }
        if(di <= 10000) ++check[di];
    }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    CheckNotSelfNum();
    // 셀프 넘버 출력
    for(int i=1; i<=10000; ++i)
        if(!check[i]) cout << i << '\n';

    return 0;
}

이렇게 넣고 돌리니 시간 제한 1초인데도 TLE가 떴다. 엥?? 뭐… 넉넉하게 잡아도 4X10000+10000 해서 50000번 밖에 안 돌아가는데 1초에서 TLE?? 이번에는 똑같은 시간 복잡도지만 수열 함수만 따로 빼서 구현했다.(C++11)

#include <iostream>
using namespace std;
// 수열 함수 d(n)
int d(int n){
    int res = n, temp = n;
    while(temp){
        res += temp%10;
        temp /= 10;
    }
    return res;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int check[10001]={0, };
    int dn;

    // 셀프 넘버 아닌 수 체크
    for(int i=1; i<=10000; ++i){
        dn = d(i);
        if(dn <= 10000) ++check[dn];
    }
    // 셀프 넘버 
    for(int i=1; i<=10000; ++i){
        if(!check[i]) cout << i << '\n';
    }

    return 0;
}

그랬더니 TLE 안뜨고 실행시간 0ms 떴다 ㅋㅋㅋㅋㅋ 왜 그러냐 대체

4) 피드백 + 다른 정답들

CheckNotSelfNum() 만들어서 돌릴 때랑 d(n) 만들어서 돌릴 때랑 무슨 차이가 있는지 알아봐야 겠다. 그리고 n<d(n)이 성립함을 이용하면 for문 2개 쓸 필요도 없음을 깨달았다. 그냥 처음 for문에 출력문까지 넣어버려도 된다.