[백준/C++/ICPC] 4090번 뱀파이어 숫자

---

오랜만에 골드를 풀어서 그런지 대략 일주일 걸린 것 같다.

처음 문제를 봤을 때는 안에 있는 숫자들을 순열로 뽑아서 나누는 지점을 정해서 브루트포스로 돌리면 답이 나올 것 같았다.

그런데 뱀파이어 숫자가 아닌 수를 입력으로 주는 경우 뱀파이어 숫자이며 input보다 큰 숫자 중 가장 작은 숫자를 출력에서 멘붕이 왔다.

 

내가 말한 방법은 100% 또 다시 x보다 큰 뱀파이어 숫자를 여러번 찾는 과정에서 시간 초과가 날 것 같았다.
(10초라는 후한 시간이 있어 시도해볼까 싶다가 최근 정답률이 너무 떨어져서 신중해졌다.)

 

오늘 다시 곰곰히 생각해보다 문제를 쪼개보기로 결정하였는데 문제를 나눠보다보니 더 좋은 방법이 떠올랐고 뱀파이어 숫자 구분 함수를 아래와 같이 2개의 문제로 나눴다.

1. 사용한 숫자가 모두 같은 것을 찾는 함수
2. 공약수를 찾는 함수

뱀파이어 숫자의 정의가 결국 공약수 중에 등장하는 숫자가 같은 숫자인데 2개의 함수로 나눠 생각하면 브루트포스보다 시간이 단축될 것이라고 생각하게 되었고 정답을 받게 되었다.

두 과정을 합쳐도 최대 Nlog^(N)이거나 100만 제곱보다는 훨 작을 것이다. 

---

/**
 * @file 4090.cpp
 * @date 2023-02-02
 */
#include <bits/stdc++.h>
using namespace std ;
int x ;
bool flag ;

bool is_vampire(int x)
{
    flag = 0 ;
    string origin = to_string(x), divided = "" ;
    for(int i = 2 ; i * i <= x ; i++)
    {
        if(x % i == 0)
        {
            divided = to_string(i) + to_string(x / i) ;
            sort(origin.begin(), origin.end()) ;
            sort(divided.begin(), divided.end()) ;
            if(divided.compare(origin) == 0)
            {
                flag = 1 ;
                break ;
            }
        }
    }

    return flag ? true : false ;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0) ;
    while(1)
    {
        cin >> x ;
        if(x == 0) break ;

        while(!is_vampire(x)) ++x ;
        
        cout << x << '\n' ;
    }
}

---

느낀점: 잘 생각해보자 그리고 최대효율을 고민하자. 수학적인 힌트가 문제에 다 있다.

문제링크: https://www.acmicpc.net/problem/4090

4090번: 뱀파이어 숫자