[2021 ICPC Sinchon Summer Algorithm Camp Contest] BOJ - 22950 이진수 나눗셈 출제 후기 및 풀이

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

[출제 후기]

 이 문제는 학기 중에 "운영체제" 과목을 공부하다 고안하게 된 문제이다. 특정한 이진수가 2의 제곱의 형태의 수로 나누어 떨어지는지 확인하고 풀어야 하는 문제가 있었는데 처음에 단순히 직접 제곱해서 문제를 풀다가 이진수의 뒷 부분에 위치한 0의 개수가 2의 K제곱의 K만큼 존재하면 나누어 떨어지기 때문에 뒷 부분에 위치한 0의 개수만 확인하면 된다는 사실을 깨닫고 문제로 출제하면 좋을 것 같다는 생각이 들어 Camp Contest의 문제로 출제하게 되었다.

 

[문제 풀이]

 위 영상은 스트리밍에 사용되었던 문제 풀이 영상이다.

 이진수 나눗셈 문제는 이진수의 각 자리 수가 2의 제곱의 형태로 나타남을 이용한 문제이다. 내가 출제하면서 의도했던 정해 풀이는 stack에 이진수 M의 각 자리 수를 넣고 pop을 진행하며 K만큼 동안 확인하며 그 사이에 1이 나온다면 "NO"를 스택이 먼저 비게 되거나 반복문을 마치게 되면 "YES"를 출력하는 것이다.

 추가적으로 영상에서는 설명하지 않았었지만 주의해야 할 예외 케이스를 이야기하자면 K가 N보다 큰 경우도 고려해 주어야 했다. 예를 들어 N이 1이고 이진수 M이 0, K가 2일 경우 이진수 M이 0이기 때문에 어떤 수로 나누든 나누어 떨어지는 것이기 때문에 "YES"를 출력해 주어야 하기 때문이다. 

[정해 코드]

#include<iostream>
#include<algorithm>
#include<stack>
#include<cstdio>
 
using namespace std;
 
stack<int> num;
 
int main(){
    int n, k;
    
    scanf("%d", &n);
    
    for(int i =0; i<n; i++){
        int m;
        
        scanf("%1d", &m);
        
        num.push(m);
    }
    
    scanf("%d", &k);
    
    for(int i =0; i<k; i++){
        if(num.empty()){
            break;
        }
        
        int top_num = num.top();
        num.pop();
        
        if(top_num != 0){
            printf("NO");
            return 0;
        }
    }
    
    printf("YES");
}