[백준 알고리즘] 백준 22950번 이진수 나눗셈 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 22950번 이진수 나눗셈 파이썬(Python)

1) 문제번호 : 22950번

 

2) 문제 출처

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

22950번: 이진수 나눗셈

 

2. 문제

이진수 M이 2^K으로 나누어 떨어지는지 여부를 판별하는 프로그램을 작성하시오. 이 때, 나누어 떨어진다는 것은 나머지 없이 정수 몫으로 나누어진다는 것을 의미한다.

 

3. 제약사항

 

4. 입력

첫 번째 줄에는 이진수 M의 자리수인 N (1≤N≤1000000)이 주어진다.

두 번째 줄에는 이진수 M이 N자리만큼 주어진다. 이진수 M의 앞부분에는 불필요한 0이 올 수 있다.

세 번째 줄에는 나누는 수 2^K의 K (0≤K≤1000000)가 주어진다.

 

5. 출력

이진수 M이 2^K으로 나누어 떨어진다면 YES, 나누어 떨어지지 않는다면 NO를 출력한다.

 

6. 풀이

- 이 문제를 푸는데 조금 걸렸다.

- 2진수 나눗셈은 K값 만큼 2진수의 오른쪽에서부터 0의 갯수가 있다면 나눠진다.

- 즉, K가 2이고 2진수가 100이면 나눠진다.

- 하지만, 0의 갯수가 K에 도달하기도 전에 1이 있으면 나눠지지 않는다.

- 여기서 1가지의 또 예외는 M이 0000일 때도 처리를 해야 한다는 것이다.

- 아래의 코드에서 만약에, N이 4고 M이 0000이면 K가 무엇이든 나눌 수 있기 때문에 YES 출력해야 한다.

 

7. 소스 코드

import sys
import math
input=sys.stdin.readline

N = int(input()) # M의 자릿수
M = list(input().rstrip()) # 2진수
K = int(input()) # 2의 지수

# 만약에, N이 4고 M이 0000이면 K가 무엇이든 나눌 수 있기 때문에 YES 출력
if '1' not in M :
    print("YES")
    exit(0)

# K가 0이라면 나누는 값은 1이 되기 때문에 YES 출력
if K == 0 :
    print("YES")
    exit(0)

count = 0 # 오른쪽에서부터 0의 갯수
for i in range(len(M)-1, -1, -1) :
    if M[i] == '1' : break
    if M[i] == '0' : count += 1

if count >= K : print("YES")

else : print("NO")

 

---