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

2024. 2. 14. 06:29Diamond/Diamond IV

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 $가 공백으로 구분되어 주어진다. (1m200 000, 0q3m3) 큰 정삼각형의 꼭짓점은 삼각격자에서 (0,0), (m,0), (0,m)이다.

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

dx축과 이루는 각도를 의미하며 0,60,120 중 하나이다. d0이면 직선 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=mxy=ml인 직선으로 생각해 보자. 당연히 z=cx+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+bm이어야 한다. x=a,z=c의 교점은 (a,m(a+c)이고, 이게 y=0을 넘어가면 안 되니 반드시 a+cm이어야 한다. 마지막으로 y=b,z=c의 교점은 (m(b+c),b)이고, 이게 x=0을 넘어가면 안 되니 반드시 b+cm이어야 한다.

 

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

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

aAxabBxbcCxc

 

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

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

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

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

 

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

 

728x90

'Diamond > Diamond IV' 카테고리의 다른 글