사용자 도구

사이트 도구


ps:problems:boj:3036

ps
링크acmicpc.net/…
출처BOJ
문제 번호3036
문제명
레벨실버 3
분류

기초

시간복잡도O(nlogm)
인풋사이즈n<=100, m<=1000
사용한 언어Python
제출기록31312KB / 72ms
최고기록52ms
해결날짜2021/08/22

풀이

  • 반지름은 원둘레랑 비례하니까 회전수의 비는 역수가 된다.
  • A/B를 기약분수로 표현하기 위해서는 분자 분모의 최소 공약수를 구해서 나눠주면 된다.
  • 최소공약수는 O(logm)에 구할수 있으므로 총 시간 복잡도는 O(nlogm)

코드

"""Solution code for "BOJ 3036. 링".

- Problem link: https://www.acmicpc.net/problem/3036
- Solution link: http://www.teferi.net/ps/problems/boj/3036
"""

import math


def main():
    N = int(input())  # pylint: disable=unused-variable
    radiuses = [int(x) for x in input().split()]
    for rad in radiuses[1:]:
        g = math.gcd(radiuses[0], rad)
        numer, denom = radiuses[0] // g, rad // g
        print(f'{numer}/{denom}')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
V B K S C
 
ps/problems/boj/3036.txt · 마지막으로 수정됨: 2021/08/22 15:35 저자 teferi