[BOJ / 백준] 1407 2로 몇 번 나누어질까 (G4^ / 수학) - Python

링크

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

 

 

 

 

문제 해석

a, b 사이의 숫자 중 2의 거듭제곱으로 나누어 떨어지는 수는 2의 거듭제곱을, 그렇지 않으면 1을 더한 결과를 출력하기

 

 

입력

첫 번째 줄 : a, b

  a : 숫자의 시작 범위

  b : 숫자의 마지막 범위

 

 

 

 

풀이 & 코드 해석

다른 문제를 푼 사람들의 코드들은 굉장히 효율적이고 간결한데, 저는 수학을 잘 못해서 무식하게 풀었습니다.

 

저는 단순하게 1~b 사이에 2의 제곱 값을 구하고 1~(a-1)사이에 2의 제곱 값을 구해서 뺀 결과와,

a~b 사이의 1의 개수를 더한 값을 결과로 출력하는 방식을 생각했습니다.

 

 

 

https://angelplayer.tistory.com/563

[BOJ / 백준] 15996 팩토리얼 나누기 (S3^ / 수학) - Python

2의 제곱 구하기는 앞에서 풀었던 팩토리얼 나누기와 유사하게 2^1, 2^2, 2^3,... 과 같이 제곱 수를 올려가면서 해당하는 값을 찾았습니다.

 

이번 문제는 2제곱의 개수를 구하는 것이 아닌 거듭제곱한 결과를 더한 값을 찾아야 하므로 코드에 해당 로직을 추가하였습니다.

 

 

 

홀수의 개수 구하는 공식은 ChatGPT가 알려준 방식이 좋아서 이후로도 정리해서 사용하려고 하는데요.

 

 

범위 내 첫 번째 홀수와 범위 내 마지막 홀수를 구해서,

차를 구한 후,

2로 나누어 주고,

마지막으로 1을 더하면 홀수의 개수를 구할 수 있다고 합니다.

 

 

 

 

코드

a, b = list(map(int, input().split()))

d = a - 1

d_ans = 0
dt = 2
while True:
    d_now = d // dt

    if d_now == 0:
        break

    if dt == 2:
        d_ans = dt * d_now
    else:
        d_ans = d_ans - ((dt // 2) * d_now) + (dt * d_now)
    dt = dt * 2


b_ans = 0
bt = 2
while True:
    b_now = b // bt

    if b_now == 0:
        break

    if bt == 2:
        b_ans = bt * b_now
    else:
        b_ans = b_ans - (bt // 2) * b_now + bt * b_now
    bt = bt * 2

# 홀수 개수 구하기
if a % 2 == 0:
    a += 1
if b % 2 == 0:
    b -= 1

odd = (b - a) // 2 + 1

print((b_ans - d_ans) + odd)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java