배수 찾기(BOJ 4994번)

문제

이미지 클릭

문제 설명

오직 1과 0으로 이루어진 숫자 m 중에서 입력받은 n으로 나누어진 숫자를 출력하는 문제입니다. 처음에는 m이 백자리가 넘어가지 않는다는 부분을 보고 너비우선탐색이 불가능하다고 판단하였지만 n이 200 이하이기 때문에 long long 범위 안에서 해결가능하기 때문에 너비우선탐색을 이용하여서 문제를 해결할 수 있습니다.

 

문제 해설

제일 먼저 n이 0일 때 종료한다는 조건을 명시 해주었습니다.

if(n==0)return 0;

 

그런 다음 우선순위 큐를 사용하여서 작은 숫자들을 위주로 너비우선탐색을 돌려주었습니다. 이때 queue를 처음 만들었을 때 1을 기본 값으로 넣어주어야 합니다. 

priority_queue<ll,vector<ll>, greater<ll>> q;
q.push(1);

 

본격적인 너비우선탐색을 하는 부분은 기본적인 너비우선탐색과 비슷한 메커니즘을 따라서 가면 풀이가 가능합니다. while문의 종료조건은 x가 n으로 나누어진다면 x를 바로 출력하면 되고, 아니라면 1과 0만을 가지는 수를 q에 넣어주어야 하는데, 이러한 값은 10 곱하거나 그 값에 1을 더한 값이 가능합니다. 

while(!q.empty()){
      ll x=q.top();
      q.pop();
      if(x%n==0){
        cout<<x<<"\n";
        break;
      }
      else{
        q.push(x*10+1);
        q.push(x*10);
      }
    }

 

최종 코드

#include<iostream>
#include<queue>
using namespace std;
int n;
typedef unsigned long long int ll;
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  for(;;){
    cin>>n;
    if(n==0)return 0;
    priority_queue<ll,vector<ll>, greater<ll>> q;
    q.push(1);
    while(!q.empty()){
      ll x=q.top();
      q.pop();
      if(x%n==0){
        cout<<x<<"\n";
        break;
      }
      else{
        q.push(x*10+1);
        q.push(x*10);
      }
    }
    while(!q.empty())q.pop();
  }
}