[Python] 10166번 관중석

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

10166번: 관중석

---

 

24/02/13

 

 

실버 1치고는 많은 고민을 하게 한 문제이다. 각 코드 별로 어떠한 흐름을 가지고 생각했는지 적어보고자 한다.

---

 

문제 접근 방식:

 

 

처음으로 생각한 것은, 보이는 관중석이 어떤 일정한 규칙을 가지고 있어서, 그 규칙이 수식으로 표현 될 것이라는 생각이 들었다.

 

그 이후에 바로 보인 사실은, $i < j$일때, 반지름 $i$가 반지름 $j$인 원을 가린다면, 그 가리는 관중석의 개수는 $\mathrm{gcd}(i, j)$와 같다는 사실이었다.

 

이후 이차원 배열 $D$를 선언했다.

 

$D[i][j]$는 반지름 $i$를 가지는 원이 반지름 $j$를 가지는 원을 가릴 때, 반지름 $i$가 가리는 관중석의 개수를 의미한다.

 

$D[i][j] = \mathrm{gcd}(i, j)$이므로, 이를 잘 이용해서 쉽게 구할 수 있을 것이라고 생각했다.

 

처음 생각한 방법은 단순히 $D[i][j]$의 구간 합을 구하는 방법이었다.

 

당연히 오답을 내놓는 풀이고, 별로 깊이 생각하지 않고 맞을 것이라고 기대하고 제출한 풀이이기 때문에 완전히 틀린 접근이었다.

 

그러다가 수식적 접근이 아니라, 원형으로 된 관중석을 직선으로 모두 펴서 생각해 보면 어떨까는 아이디어가 나왔다.

 

예를 들어, 다음 그림과 같다.

 

$i=2, 3, 6$일 때의 모습

 

위의 그림은 각각 반지름 $i = 2, 3, 6$일 때를 일직선으로 핀 모습을 나타낸다.

 

이때 서로 다른 직선의 겹치는 빨간 선은 이미 가려지는 관중석이라고 생각할 수 있다.

 

저 직선을 $0$과 $1$ 사이의 실수를 나타낸 수직선으로 생각한다면, 우리는 저 빨간 선을 유리수로 나타낼 수 있다.

 

예를 들어 저 그림의 두 번째 예시는 $\frac{1}{3}, \frac{2}{3}, \frac{3}{3}$으로 표현할 수 있다.

 

빨간 선이 겹친다는 의미는, 서로 다른 빨간 선이 나타내는 두 수가 실질적으로 같음을 의미한다.

 

즉, 위의 그림에서는 $\frac{1}{3}$과 $\frac{2}{6}$이 같음을 알 수 있다.

 

이를 발견하고 나서, 나는 파이썬의 Fractions 모듈을 활용해 구현을 할 수 있었다.

 

이중 반복문을 활용해 주어지는 범위에서 만들 수 있는 모든 유리수들을 만들고 이를 set을 통해 중복을 없애주었다.

 

결과는 마지막 서브테스크에서 메모리 초과를 받았다.

 

기본적으로 Fractions 모듈을 활용하면 메모리를 많이 차지하기 때문에 매우 불리하다.

 

Fractions 모듈을 활용하지 않고, gcd를 나눠준 (분자, 분모) 튜플을 set에 넣어주는 방식으로 구현했다.

 

이 또한 메모리 초과를 받았는데, 파이썬에서 set이 메모리를 많이 차지함을 알고, 이를 $\textrm{count}$라는 배열로 바꿔서 표현해보고자 했다.

 

즉, $\textrm{count}[i][j] = 1$이라면, 분자가 $i$이고 분모가 $j$인 분수가 이미 있음을 표현하는 것이다. ($\mathrm{gcd}(i, j) = 1$)

 

수가 최대 $2,000$까지 주어지므로, $\textrm{count}$배열은 $2,000 \times 2,000$크기의 $2$차원 배열인 셈이다.

 

이를 sum함수를 통해 주어진 범위만큼 더해주었고, 최종적으로 메모리까지 줄여 맞았습니다를 받을 수 있었다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 10166번 관중석
# 수학
'''
접근 방법:
D[i][j] = gcd(i, j)
반지름 i를 가지는 원과 반지름 j를 가지는 원이 있으면,
반지름 i에 의해 가려지는 좌석의 개수
'''
from math import gcd
D1, D2 = map(int, input().split())
count = [[0 for _ in range(2001)] for _ in range(2001)]
for i in range(D1, D2+1):
    for j in range(1, i):
        k = gcd(i, j)
        count[j//k][i//k] = 1
print(sum(sum(count[i]) for i in range(2001))+1)