BOJ 13949 - 쉬운 문제 (Python3)

백준에는 가끔씩 농도가 너무 높은 수학 문제들이 올라온다. 구현보다는 수학에 강점이 있는 나에게는 그런 문제들이 아주 맛 좋은 먹잇감이다. 오늘의 문제인 쉬운 문제도 그러하다.

글을 쓰는 지금 기준 Diamond III이라는 정말 높은 난이도를 자랑하지만 내가 이 문제를 보고 구현을 마치기까지 걸린 시간은 1시간도 안 걸렸다. 그렇다고 단체로 착각해서 이 문제를 어렵게 봤다는 말은 아니다. 제목 값을 전혀 하지 못하는 문제 중 하나라고 감히 자부까지 할 수 있다. 다만 이 문제의 풀이법이 KMO에서는 너무나도 웰노운이었을 뿐...

 

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

---

문제

1보다 큰 정수 \(k\)가 주어졌을 때, 다음 식을 만족하는 양의 정수 \((a, b, c)\)는 무수히 많다는 것을 증명할 수 있다: $$a^2+b^2+c^2=k(ab+bc+ca)+1$$

양의 정수 \(n\)과 \(k\)가 주어졌을 때 위 식을 만족하는 임의 \(n\)개의 \((a_1,b_1,c_1),(a_2,b_2,c_2)\cdots(a_n,b_n,c_n)\)을 찾아라. \(a_1,\cdots,a_n,b_1,\cdots,b_n,c_1,\cdots,c_n\)은 서로 다른 양의 정수이고, 최대 100자리 수이다.

 

입력

첫째 줄에는 두 정수 \(k\)와 \(n\)이 주어진다. \((2\le k\le 1000, 1\le n\le 1000)\)

 

예제 입력)

# 예제 입력 1
2 8

# 예제 입력 2
3 3

 

출력

각 줄에 세 수 \(a,b,c\)를 출력하라.

 

예제 출력)

# 예제 출력 1
1 2 6
3 10 24
12 35 88
15 28 84
4 5 18
14 33 90
40 104 273
21 60 152

# 예제 출력 2
1 3 12
8 21 87
44 165 615

 

---

내 코드

from collections import deque
def shift(a,b,c): return (b,c,a)
k,n = map(int,input().split())
Q = deque([(0,1,k)]); v = {0}
while True:
    a,b,c = Q.popleft()
    if (a-b)*(b-c) != 0:
        if a not in v and b not in v and c not in v:
            print(a,b,c); n -= 1
            v.add(a); v.add(b); v.add(c)
            if n == 0: quit()
    for _ in range(3):
        temp = k*(a+b)-c
        if temp > 0: Q.append(tuple(sorted([a,b,temp])))
        a,b,c = shift(a,b,c)

 

일단은 이 문제에서 양의 정수라는 제약만 없앤다면 자명한 해 하나를 얻을 수 있다. \((a,b,c)=(0,1,k)\)이다. (이게 진짜 해가 되는지 아닌지는 매우 쉽게 검증할 수 있으니 이 글을 읽는 사람에게 검증을 맡긴다.)

그리고 정수 계수의 이차방정식이 최고차항의 계수가 1이고, 한 근이 정수라면 당연히 나머지 한 근도 정수이다. 왜? 근과 계수의 관계에 의해서. \(x^2-sx+t=0\)의 두 근이 \(x=\alpha,\beta\)이면서 \(s, t, \alpha\)가 모두 정수라면 \(\beta=s-\alpha\)이므로 \(\beta\)도 정수가 될 수 밖에 없다.

이렇게 근과 계수의 관계(Vieta's formula)를 통해서 한 근을 이용하여 다른 하나의 근을 얻는 것은 이미 수학 올림피아드에서 반쯤 정석으로 굳어져 있다. Vieta jumping이라는 멋있는 이름도 있다! 대표적인 문제로 IMO의 전설적인 문제, 1988 IMO Problem 6이 있다. 그 테렌스 타오도 7점 만점에 1점밖에 얻지 못한 극악의 문제이나, 현재는 반쯤 정석이 되어 있어 KMO를 준비하는 학생들도 한 번쯤 보고 넘어가는 문제가 되었다.

 

여하튼 그 Vieta jumping을 이용해서, 한 정수해를 통해서 하나의 새로운 해를 만들어낼 수 있다.

식을 잘 정리해서 \(c\)에 대한 이차방정식으로 만들어 보자. 그러면 \(c^2 - k(a+b)c + (a^2+b^2-kab-1) = 0\)이 된다. 두 근의 합이 \(k(a+b)\)이고 한 근이 \(c\)이므로, 다른 한 근은 \(C=k(a+b)-c\)이어야 한다. 게다가 \(k,a,b,c\)가 모두 정수가 되므로 \(C\)도 정수가 된다.

방금 정수해 \((a, b, c)\)에서 \((a, b, C)\)를 만들어 낸 셈이다.

 

이제 그래프 탐색하듯이 기존 해로 새로운 해를 만들어 내면 된다. 한 번 쓴 수를 다시 쓰지 않도록 집합이나 리스트에 잘 저장한 다음 큐를 이용한 간단한 수준의 BFS를 돌리는 것만으로 1000개는 물론이요 더 많은 해를 얻어낼 수 있다!

 

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