[백준] 10166번 관중석 _ Python

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

10166번: 관중석

 

 

---

 

1. Preview

시간 복잡도: O(N^2)

 

공간 복잡도: O(N^2)

 

참고 : https://burningjeong.tistory.com/525

 

유형: 수학

 

 

---

 

2. 초기 접근 방법

각도에 따라 의자를 배치하도록 했다.

하지만 이 방법은 부동소수점 오차로 인해, 기존에 놓았던 각도인지 판별이 불가능하다.

circle = set()

for i in range(a, b+1):
    init = 360 / i
    k = init

    if init not in circle:
        while init <= 360:
            circle.add(init)
            init += k

print(len(circle))

 

 

---

 

3. 생각

a부터 b까지 1 ~ a까지 1바퀴씩 돌게 된다.

이 때 최대 공약수로 나눠주면서 '기약 분수' 형태로 만들어 같은 각도에 있는 좌표들을 추가해주지 않으면 된다.

for i in range(a, b+1):
    for j in range(1, i+1):
        g = gcd(i, j) # 최대 공약수
        
        a = i // g
        b = j // g

        if not check[a][b]:
            result += 1
            check[a][b] = 1

 

 

---

 

4. 코드

# 아.. 수학 문제 싫다

# 파이썬 시간초과..
    # 라이브러리 gcd
    # check 배열 b 크기에 맞춰 할당
    # 한 줄인데 readline까지
    # == 0, not으로

from sys import stdin
from math import gcd

a, b = map(int, stdin.readline().split())
check = [[0] * (b+1) for _ in range(b+1)]

result = 0
for i in range(a, b+1):
    for j in range(1, i+1):
        g = gcd(i, j) # 최대 공약수

        a = i // g
        b = j // g

        if not check[a][b]:
            result += 1
            check[a][b] = 1

print(result)