[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number

just store Lunlun numbers in an array.좋은 문제를 발견하면, 그 문제의 뽕을 뽑아먹는(충분히 검토하는) 코뽕시간입니다 ㅎ

오늘의 코뽕문제는 AtCoder Beginner Contest 161 - D Lunlun Number가 되겠습니다.

이 문제는 설명이 단순하고 쉽기 때문에 나중에 다시 문제를 recall하기도 좋고 풀이도 다양해서 코뽕에 아주 적합한 문제가 되겠습니다.

참고로 이 Lunlun number는 OEIS에 등록되어 있습니다.

이문제는 대략 살펴보아도 

브루트포스, 백트래킹, 이진탐색, Queue 등을 이용해서 풀 수 있는걸로 보입니다.

브루트 포스를 이용한 방법

먼저 브루트포스를 이용한 방법은, 단순히 1씩 증가시키면서 lunlun 넘버인지 보는코드에다가 일정부분을 스킵할 수 있는 코드를 삽입하는 간단한 방법입니다. 샘플코드는 다음과 같습니다.

예들들어 현재 숫자가 243일때 2가 violation이므로 둘째자리 숫자인 4가 9가 될때까지 50을 더해서 293까지 skip한다는 idea. 

 
ll lun[100001];
int check_lunlun(ll i) {
    int a = -1;
    int jari = 1;
    while (i) {
        int ii = i % 10;
        if (a == -1) a = ii;
        else if (abs(a - ii) > 1) {
            if (a > ii && a < 9)
                return (jari / 10) * (10 - a - 1);
            else return 1;
        }
        i /= 10; jari *= 10, a = ii;
    }
    return 0;
}
int main() {
    int K; scanf("%d", &K);
    int k = 1;
    for (ll i = 1; k <= K; i++) {
        ll skip = check_lunlun(i);
        if (skip == 0) lun[k++] = i;
        else i += skip - 1;
    }
    printf("%lld\n", lun[K]);
    return 0;
}

이정도 아이디어만 가지고도 AC를 받기에는 충분(대략 700ms정도 걸림)

다른 아이디어도 적용하면 좀 더 스킵할수도 있을것임

아래는 다른사람들 방법

just store Lunlun numbers in an array.

근데 이건 원리상 아래 BFS랑 동일한거 같다.

백트래킹을 이용한 방법

678이라는 임의의 Lunlun넘버를 생각해 봤을때, 다음처럼 3가지 경우로 갈 수 있다고 생각하고, DFS를 돌리는 아이디어.

이건 실전에서 구현하기도 좋아보인다. 

map<ll, int> m;
void dfs(ll i) {
    m[i] = 1; 
    if (i > 3234566667ll) return;
    int ld = i % 10;
    if(ld+1<=9) dfs(i * 10 + ld + 1);
    dfs(i * 10 + ld);
    if(ld-1>=0)dfs(i * 10 + ld - 1);
}
int main()
{
    for (int i = 1; i < 10; i++) dfs(i);
    int k; cin >> k;
    int ix = 1;
    for (auto a : m) {
        if (ix++ == k) cout << a.first << endl;
    }
    return 0;
}

특별히 백트래킹이랄것도 없고.. 그냥 최대숫자보다 커지면 return하는게 다인데.. 저 최대숫자를 모르면 좀 애매하다는게 문제라면 문제.. DFS특성상 11111111111111 이런숫자를 먼저 최대자리수까지 파는 경향이 있기 때문에 더욱그렇다.

BFS를 이용한 방법

에디토리얼에서도 이걸 정해로 주장하고 있다.

뭐 기본적으로 DFS와 동일한 아이디어 인데, 최대숫자를 guessing할 필요가 없고 그냥, 값이 채워진게 10만번째이면 바로 break하면 되기 때문에 좀 더 안전성이 있다. 부채모양으로 퍼져나가니 찾자마자 최단거리가 되는 원리랑 조금 비슷한게 담긴거 같다.

 
map<ll, int> m;
int main()
{
    int k; cin >> k;
    queue<ll> q;
    for (int i = 1; i < 10; i++) q.push(i);
    while (q.size()) {
        ll n = q.front(); q.pop();
        m[n] = 1;
        if (m.size() > 100000) break;
        if(n%10!=0) q.push(n * 10 + n % 10 - 1);
        q.push(n * 10 + n % 10);
        if(n%10!=9) q.push(n * 10 + n % 10 + 1);
    }
    int ix = 1;
    for (auto a : m) {
        if (ix++ == k) cout << a.first << endl;
    }
    return 0;
}

실전에서는 이코드처럼 정확히 10만에서 break하면 좀 위험할수도 있으니, 좀더 버퍼를 주는게 좋겠지만, 어쨌든 DFS보다는 나은 어프로치인듯하다.

덕북에 실행속도와 메모리 사용량에 있어서도 3배정도는 이득이 있는듯?

아래는 다른사람들 BFS구현

https://atcoder.jp/contests/abc161/submissions/11513177

https://atcoder.jp/contests/abc161/submissions/11518213

이진탐색을 이용한 방법

이진탐색+DigitDP 솔루션 : https://atcoder.jp/contests/abc161/submissions/11532810

이건 오버 엔지니어링 같아서 보기가 좀 싫어지네 ㅎ 나중에 보자.