BOJ 22356 - 종이, 펜, 삼각형 (Python3)

2월 12일에 SUAPC 대비를 위한 팀연습을 치뤘다. 우리 팀 중 한 명은 갑작스럽게 잡힌 일정에 대비하지 못해서 대타 버스기사 kiwiyou를 데리고 팀연습을 치루었다. 상대 팀은 전 ICPC 팀메이트였던 changhw의 팀. 진짜 강적이었다... kiwiyou가 빡구현 문제, blackstar0223이 아이디어성이 높은 그리디 문제에서 승리하지 못했으면 내가 구멍이 되었을 것이다. 난... 3문제를 풀기는 했는데 발목에 추만 달아 준 느낌이라...

셋은 UCPC 2021 예선. 내가 B, F, G를, blackstar0223이 C, D를, 그리고 kiwiyou가 A, I를 잡아내서 7문제를 풀 수 있었다. 그런데 이거 3시간 셋을 억지로 5시간으로 늘린 거라 이 멤버로 했어도 본선은 못 갔을 것 같다 ㅋㅋㅋ.

문제 중 F번이 누가 봐도 수학이라 나에게 넘겨졌는데, 처음에는 보기만 해도 개끔찍해서 내가 풀 수 없을 거라고 생각했지만 어찌어찌 잡고 아이디어를 생각해 봤더니 풀렸다. 내가 할 수 있는 게 전부 죽어버린 시점이라 손을 댈 수 있었으니 이런 강운이 발생하기를 바라야 하는 걸까 그렇지 않기를 바라야 하는 걸까? 아무튼. 

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

삼각형은 의외로 위대하다. 원은 만 3세면 따라그릴 수 있으며, 사각형은 만 4세면 그릴 수 있다. 그러나 삼각형은 그보다 1년은 더 지나야 그릴 수 있다고 알려져 있다 (안효섭, 신희영, 『홍창의 소아과학』, 미래앤(2020), 12판). 이하는 만 5살이 된지 한참 되었기 때문에, 무리 없이 종이에 펜으로 변의 길이가 \(m\)인 '큰 정삼각형'을 하나 그렸다.

이하의 호기심을 조금 더 알아보기 전에 삼각격자에 대한 정의가 필요하다. 좌표평면에서 \( x \)축이 \( y \)축과 직각을 이루는 직각좌표계와는 달리, 삼각격자는 다음 그림과 같이 \( x \)축과 \( y \)축이 이루는 각도가 60도이다. 여기에 \(x + y = m\) 꼴의 직선을 그으면 다음 그림과 같이 \( (0,0) ,  (m,0) ,  (0,m) \)을 꼭짓점으로 갖는 정삼각형이 하나 만들어진다. 이 정삼각형을 '큰 정삼각형'이라고 하자.

그림 F.1: 삼각격자의 양 축과 x+y=m 꼴 직선

이하는 더더욱 많은 정삼각형을 그리고 싶어서, 세 변 중 하나에 평행하면서 큰 정삼각형의 내부를 지나가는 직선을 \(q\)개 그은 다음 큰 정삼각형에 포함되지 않는 부분은 지워 버렸다. 그러자 정삼각형이 꽃처럼 피어났다!

이하는 수많은 정삼각형을 보며 행복해졌으나, 이내 그림에 정삼각형이 총 몇 개나 있는지 궁금해졌다. 손으로 세기에는 너무 많아 보이니, 이하의 질문에 답할 수 있는 프로그램을 작성해 보자.

 

입력

첫째 줄에는 큰 정삼각형의 한 변의 길이를 나타내는 정수 \( m \)과 이하가 새로 그은 직선의 개수 $ q $가 공백으로 구분되어 주어진다. \( ( 1 \leq m \leq 200\ 000 \), \( 0 \leq q \leq 3m-3)\) 큰 정삼각형의 꼭짓점은 삼각격자에서 \( (0,0) \), \( (m,0) \), \( (0,m) \)이다.

그 다음 \( q \)개의 줄에는 각각 두 개의 정수 \( d \)와 \( l \)이 공백으로 구분되어 주어진다. \( ( 0 < l < m )\)

\( d \)는 \( x \)축과 이루는 각도를 의미하며 \(0, 60, 120\) 중 하나이다. \( d \)가 \( 0 \)이면 직선 \( y=l \)이, \( 60 \)이면 직선 \( x=l \)이, \( 120 \)이면 직선 \( x+y=l \)이 추가된다. 입력으로 들어오는 직선은 모두 다르다.

 

예제 입력)

# 예제 입력 1
2 3
0 1
60 1
120 1

# 예제 입력 2
10 5
60 1
120 2
0 1
120 5
60 9

 

출력

큰 정삼각형 안에 있는 정삼각형의 개수를 출력한다. 일부만 큰 정삼각형 안에 있는 정삼각형은 포함하지 않으며, 점은 정삼각형이 아니다. 큰 정삼각형도 자기 자신 안에 있다.

 

예제 출력)

# 예제 출력 1
5

# 예제 출력 2
12

 

---

내 코드

from math import ceil
from sys import stdin
import decimal
input = stdin.readline
def fft(a, b, digit = 0):
    """by teferi"""
    decimal.setcontext(
        decimal.Context(prec=decimal.MAX_PREC, Emax=decimal.MAX_EMAX))
    if digit == 0:
        digit = min(20, len(str(min(len(a), len(b)) * max(a) * max(b))))
    f = f'0{digit}d'
    a_dec = decimal.Decimal(''.join(format(x, f) for x in a))
    b_dec = decimal.Decimal(''.join(format(x, f) for x in b))
    c_dec = a_dec * b_dec
    total_digit = digit * (len(a) + len(b) - 1)
    c = format(c_dec, f'0{total_digit}f')
    return [int(c[i:i + digit]) for i in range(0, total_digit, digit)]
m,q = map(int,input().split())
if m == 1: print(1); exit(0)
a,b,c = [0]*m,[0]*m,[0]*m
a[0],b[0],c[0] = 1,1,1
for _ in range(q):
    deg,l = map(int,input().split())
    if deg == 0: b[l] += 1
    elif deg == 60: a[l] += 1
    else: c[m-l] += 1
abc = fft(fft(a,b),c)
A,B,C = [1],[1],[1]
for i in range(m):
    if i == 0: A,B,C = [0],[0],[0]
    A.append(a[i]+A[-1])
    B.append(b[i]+B[-1])
    C.append(c[i]+C[-1])
ans = A[m//2+1]*B[m//2+1]*C[m//2+1]
ans -= abc[m]
for i in range(m//2+1,m):
    ans += (B[m-i+1]*C[m-i+1])*a[i]
    ans += (C[m-i+1]*A[m-i+1])*b[i]
    ans += (A[m-i+1]*B[m-i+1])*c[i]
print(ans)

 

놀랍게도 이 문제의 풀이는 팀연습 전날 kiwiyou가 보내 준 phase diagram에서 아이디어를 얻었다. 

Phase diagram of H₂O :: Ternary phase diagram of Fe-Cr-Ni stainless steel :: Example #2

3개 물질로 이루어진 상평형도와 비슷하게 보였고, 내 전공이 화학공학인지라 phase diagram은 숱하게 봤다. 웬만해서 ternary case를 다루지는 않지만, 화공열역학 교재에서 지나가듯 한 번 나온 걸 읽는 법은 기억하고 있었다.

삼각형 내 한 점과 변과의 거리가 클수록, 해당하는 변과 마주보는 꼭지점에 할당되는 화합문의 조성이 그에 비례해서 낮아지는... 뭐 그런 이야기다. 여기서 중요한 점은 어떤 하나의 점은 세 변과의 거리가 주어져 있고 그 합이 삼각형의 높이와 동일하기만 한다면 세 변과의 거리로 일의적으로 정해진다는 것이다. 달리 말해서 어떤 한 점에서 세 변과의 거리 합이 상수라는 것이다.

 

여기서는 \(d=120\)인 직선을 \(x+y=l\) 대신 \(z=m-x-y = m-l\)인 직선으로 생각해 보자. 당연히 \(z=c\)와 \(x+y=m\) 사이의 거리는 \(c\)이다. 그러면 \(x=a,y=b,z=c\)의 세 직선이 정확하게 한 점에서 만나려면 \(a+b+c=m\)이어야 한다. 거리의 합이 상수인데, 이 때 그 상수가 어떻게 되는지는 \((x,y)=(0,m)\)과 같은 큰 삼각형의 꼭지점을 아무거나 대입하면 상수를 쉽게 얻을 수 있다.

이 때는 항상 만나는 점이 삼각형 내부에 있다. 왜냐하면 삼각형 외부에 존재하려면 \(a, b, c\) 셋 중 하나는 음수여야 하는데 입력에는 그런 케이스가 전혀 존재하지 않기 때문이다.

그러하다면 \(x=a,y=b,z=c\) 이 세 직선으로 만들어지는 삼각형이 큰 삼각형 내부에 있을 조건부터 따져 보자. \(x=a, y=b\)의 교점은 당연히 \((a,b)\)일 테고, 이게 \(x+y=m\), 곧 \(z=0\)을 넘어가면 안 되니 반드시 \(a+b\le m\)이어야 한다. \(x=a,z=c\)의 교점은 \((a,m-(a+c)\)이고, 이게 \(y=0\)을 넘어가면 안 되니 반드시 \(a+c\le m\)이어야 한다. 마지막으로 \(y=b,z=c\)의 교점은 \((m-(b+c),b)\)이고, 이게 \(x=0\)을 넘어가면 안 되니 반드시 \(b+c\le m\)이어야 한다.

 

\(a+b,b+c,c+a\le m\)을 만족시키는 것의 갯수를 세 준 다음 \(a+b+c=m\)을 만족시키는, 그래서 한 점에서 만나 삼각형을 이루지 않는 케이스를 제외해 주면 답이 나온다는 것이다. 다행히 \(a+b+c=m\)이 성립할 때는 항상 부등식도 따라 성립하기 때문에 이상한 케이스워크는 필요가 없다.

쿼리로 주어지는 각 직선의 집합을 \(A=\{a\mid x=a\text{ is given}\}\), \(B=\{b\mid y=b\text{ is given}\}\), \(C=\{c\mid z=c\text{ is given}\}\)이라고 두자. 그러면 \(|\{(a,b,c)\mid a+b+c=m\}|\)을 세는 방법은 간단하고 잘 알려져 있다. 그냥 아래 다항식의 \(x^m\)의 계수를 세면 되며, 이러한 다항식 곱은 FFT로 가능하다.

\[\sum_{a\in A}x^a\cdot\sum_{b\in B}x^b\cdot\sum_{c\in C}x^c\]

 

그렇다면 삼각형을 이룰 조건을 만족시키는 triplet \((a,b,c)\)의 수는 어떻게 구해야 할까?

우선 \(a,b,c\le \frac m2\)인 경우는 무조건 가능하다. 그렇지 않을 때 조건을 만족시키는 경우의 수를 세 보자. 대칭성을 고려하여 \(a>b,c\)로 둘 것이다.

그러면 \(a+b,a+c\le m\)이므로 단순히 \(b,c\le m-a\)이기만 하면 된다. \(b+c\le2(m-a)<2m-m=m\)이므로 나머지 부등식 하나는 고려하지 않아도 된다. 이 모든 과정은 \(A,B,C\)의 누적합 배열만 만들어 주면 금방 수행 가능하다.

아이디어가 까다로웠지만 하나하나 풀어 가는 재미가 있던 문제였다. Ternary phase diagram이 머릿속에 지나가지 않았으면 절대 못 풀었을 거다.

 

이로서 22356번의 풀이를 마친다.