[백준/파이썬] 1975번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 1975번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
창영이는 심심해서 혼자 재미 없는 게임을 하나 생각해냈다. 숫자 N을 먼저 정하고, 이 숫자를 2진법, 3진법, 4진법, …, 100만진법, 100만 1진법 등등으로 바꾸어 보면서, 마지막자리에 연속된 0의 개수를 모두 더하는 것이다.
예를 들어 N=5라면, 2진법 101, 3진법 12, 4진법 11, 5진법 10, 6진법 5, 7진법 5, … 등과 같으므로 답은 1이 된다. 여러분이 할 일은 주어진 N에 대해서 창영이가 구한 답을 찾는 것이다. 정확히 설명하기 위해 수학식으로 쓰자면, f(N, b)를 N을 b진법으로 나타냈을 때 마지막에 따르는 연속된 0의 개수로 정의 할 때
[\sum_{b=2}^{\infty}{f(N, b)}]
를 구하는 것이다.
입력 요약
첫 줄에 테스트 케이스의 수 T가 주어진다. 다음 T줄에 걸쳐서 N이 주어진다.
출력 요약
각 줄에 위 수식에 대한 답을 출력한다.
코드
import sys;read=sys.stdin.readline
r=[]
for t in range(int(read())):
n,s=int(read()),0
for i in range(2,n+1):
l=[n]
while True:
l.append(l[-1]//i)
l[-2]%=i
if l[-1]<i:break
i=0
while l[i]==0:i+=1
s+=i
r.append(s)
print('\n'.join(map(str,r)))
설명
핵심은 구현 관점에서 창영이는 심심해서 혼자 재미 없는 게임을 하나 생각해냈다. 숫자 N을 먼저 정하고, 이 숫자를 2진법, 3진법, 4진법, …, 100만진법, 100만 1진법 등등으로 바꾸어 보면서, 마지막자리에 연속된 0의 개수를 모두 더하는 것이다. …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기