December 29, 2018 15:00

청개구리는 2004년 한국정보올림피아드 지역본선에서 가장 어려운 문제인 고등부 5번으로 출제된 문제이다. 일단 국내 대회의 기출 문제이고, 문제 내용도 어렵지 않고 입력되는 값의 범위도 작아서 많은 사람들이 관심을 갖고 해결을 시도해 왔다. 하지만 오랜 기간 동안 그 누구도 맞았습니다!!를 받지 못했고¹, 문제나 데이터가 잘못되었다는 의문을 제기하는 사람도 적지 않았다. 그러나 2018년 4월 본인을 포함해 두 명의 맞은 사람이 나오면서 문제에는 이상이 없는 것으로 밝혀졌고 이 문제는 Baekjoon Online Judge에서 가장 신비로운 문제의 대명사가 되었다.

이 문제의 풀이는 관찰을 통해 규칙을 찾아 나가는 것이 주를 이루므로 일반적인 알고리즘 문제보다는 수학 문제나 퍼즐을 푸는 것에 가까운 느낌을 줄 것이다. 이 풀이를 통해 더 많은 분들이 이 문제의 매력을 느껴 주었으면 한다.

문제 소개

여러 개의 칸이 일렬로 나열된 모양의 논이 있다. 이 논에 여러 마리의 개구리가 들어와 여러 개의 칸을 밟고 지나간다. 개구리는 다음과 같은 규칙에 따라 이동한다.

• 개구리는 논의 왼쪽에서 들어와 일정한 간격으로 뛰어서 논의 오른쪽으로 나간다.
• 개구리가 뛰는 간격은 1칸 이상 6칸 이하이다.
• 논의 왼쪽 끝에서 개구리가 처음 밟는 지점까지의 거리는 개구리가 뛰는 간격 이하이다. 예를 들어 3칸 간격으로 뛰는 개구리는 논의 가장 왼쪽 세 개의 칸 중 하나를 반드시 밟는다.
• 개구리는 논에 들어오면 반드시 두 개 이상의 칸을 밟고 나간다.

문제의 목적은 각 칸을 몇 마리의 개구리가 밟았는지 주어질 때, 최소 몇 마리의 개구리가 있어야 같은 흔적을 만들 수 있는지 구하는 것이다.

이 글에서는 다음과 같은 표기를 사용한다.

• $N$ : 칸의 개수. 이 문제에서는 최대 200개의 칸이 주어질 수 있다.
• $M$ : 답의 상한. 이 문제에서는 최대 100마리의 청개구리가 등장할 수 있다.
• $A_x$ : $x$번째 칸을 밟은 개구리의 수
• $(a, b)$ 개구리 : 뛰는 간격이 $b$이고 처음 밟는 칸이 왼쪽에서 $a$번째 칸인 개구리
• $F_{a, b}$ : 어떤 배치에 속한 $(a, b)$ 개구리의 수

예시

첫 번째 접근

입력으로 각 칸을 밟는 개구리의 수가 주어지므로, 각 칸이 어떤 개구리들에 의해 밟히는지를 파악하는 것이 풀이의 첫 걸음이 될 것이다. 이 내용에서는 기초적인 관찰을 통해 문제를 수학적 언어로 표현하고 대수적으로 접근해 보도록 한다.

첫 번째 관찰

칸이 충분히 많아서 $(1, 1)$부터 $(6, 6)$까지의 개구리를 모두 사용할 수 있다면, 각각의 칸은 1부터 6까지의 서로 다른 간격을 가진 6종류의 개구리가 밟고 지나가게 된다. 또한 어떤 칸을 밟는 개구리가 논에 들어와서 처음 밟는 칸은 칸의 번호를 개구리의 간격으로 나눈 나머지와 관계가 있다. 예를 들어 27번 칸은 $(1, 1)$, $(1, 2)$, $(3, 3)$, $(3, 4)$, $(2, 5)$, $(3, 6)$ 개구리에 의해 밟히며, 이를 수식으로 표현하면 $A_{27}=F_{1,1}+F_{1,2}+F_{3,3}+F_{3,4}+F_{2,5}+F_{3,6}$이다.

따라서 이 문제는 $1+2+3+4+5+6=21$개의 미지수로 구성된 여러 개의 일차방정식이 주어질 때 모든 미지수의 합을 최소로 만드는 문제로 바꿀 수 있다.

Linear programming

Linear programming 문제란 여러 개의 일차 관계식이 주어질 때 어떤 일차식의 최댓값 또는 최솟값을 구하는 문제를 말한다. 간단한 예시를 들면 다음과 같다.

닭은 마리당 30원이고 10$m^2$의 공간을 차지한다. 오리는 마리당 20원이고 20$m^2$의 공간을 차지한다. 농부 존에게 1200원과 600$m^2$의 농장이 있을 때 닭과 오리를 합쳐서 최대한 많이 사려고 한다면 몇 마리나 살 수 있는가?

0 이상인 두 수 $x$, $y$에 대해 $30x+20y \leq 1200$, $10x+20y \leq 600$일 때 $x+y$는 최대 얼마인가?

앞선 관찰에서 우리는 청개구리 문제를 linear programming 문제로 바꿀 수 있음을 발견했다. 따라서 linear programming 문제를 풀 수 있다면 청개구리 문제도 풀 수 있을 것이다!

이 문제를 푸는 방법으로는 George Dantzig가 개발한 Simplex 알고리즘이 잘 알려져 있다. 이 풀이에서는 이 알고리즘의 동작 원리를 다루지는 않을 것이다. 중요한 것은 이 알고리즘을 구현한 코드가 여러 상위권 팀들의 팀노트에 실려 있어 쉽게 가져다 쓸 수 있다는 점이다. 알고리즘이 어떻게 답을 구하는지는 몰라도 대회에서는 일단 맞았습니다!!를 받는 것이 중요하고, 그러려고 만드는 것이 팀노트 아닌가!

본인은 실제로 주변의 여러 사람들이 이 문제를 보고 아! 심플렉스 아시는구나! 를 외치며 팀노트에서 코드를 복사해서 제출하는 것을 지켜보았다. 그러나 그 결과는 처참했다.²

왜 틀리는가?

이 문제에는 너무나 당연한 전제가 하나 깔려 있다. 바로 개구리를 여러 조각으로 자를 수 없다는 것이다. 답으로 개구리 3.5마리 를 출력할 수 있다면 문제가 너무 삭막하지 않겠는가?

...
double matrix[MAX_N + 1][MAX_M + MAX_N + 1];
double c[MAX_N + 1];
double solution[MAX_M + MAX_N + 1];
...

일반적인 linear programming 문제는 실수 범위에서 답을 구하는 것을 전제로 한다. 따라서 운이 나쁘다면 실제로 개구리 3.5마리를 답으로 출력할지도 모르는 일이다.

위의 입력을 만족시키기 위해서는 최소 4마리의 개구리가 필요하다. 그러나 개구리를 절반으로 자를 수 있다면 더 좋은 답을 찾을 수 있다!

식에 등장하는 모든 미지수의 계수가 1임에도 불구하고 정수가 아닌 답이 나올 수 있다는 것은 꽤 신선하게 느껴진다. Simplex 알고리즘으로 얻은 답을 변형해서 정수로 이루어진 답을 구하는 방법도 있기는 하지만(Cutting-plane method 등), 애초 풀이 과정에서 실수가 등장하는 이상 오차 이슈를 피하기 힘들 것이다. 적어도 라이브러리에 의존해서 편하게 넘어가려고 했던 계획은 물거품이 되었으니 새로운 길을 찾아야 한다.

두 번째 접근

이 문제를 해결하는 가장 원초적인 방법은 각 종류의 개구리의 수를 아무렇게나 정해 놓고 답이 되는지 확인하는 방법이다. 이 문제는 개구리의 종류가 21가지이고 답의 상한은 100마리이므로 약 $1.7 \times 10^{23}$가지의 가능성을 전부 확인하면 답을 구할 수 있다.

하지만 이 문제에서 주어지는 관계식들은 굉장히 규칙적이므로, 이를 잘 이용하면 답의 후보를 많이 줄일 수 있는 실마리를 발견할 수 있을지도 모른다. 이 풀이에서는 여러 관찰을 통해 답의 후보를 충분히 줄이는 것을 목적으로 한다.

두 번째 관찰

어떤 두 가지의 개구리 조합이 같은 흔적을 만든다면, 당연히 개구리의 수가 더 적은 조합을 선택하는 것이 이득이다. 예를 들면 다음과 같은 경우들이 있다.

• $(1, 2)$ 개구리와 $(2, 2)$ 개구리를 동시에 사용한다면 그 대신 $(1, 1)$ 개구리를 사용하는 것이 이득이다.
• $(2, 4)$ 개구리와 $(4, 4)$ 개구리를 동시에 사용한다면 그 대신 $(2, 2)$ 개구리를 사용하는 것이 이득이다.
• $(1, 6)$, $(3, 6)$, $(5, 6)$ 개구리를 동시에 사용한다면 그 대신 $(1, 2)$ 개구리를 사용하는 것이 이득이다.

어떤 개구리들의 조합이 더 나은 대체재가 존재한다면 그 조합은 최적의 배치에서 등장하지 않을 것이다. 그 조합이 하나도 남지 않을 때까지 계속해서 대체하는 것이 이득이기 때문이다. 따라서 최적의 배치에서 그 조합에 속하는 개구리들을 전부 모아 보면 적어도 한 종류는 한 마리도 등장하지 않는다. 즉, 해당 조합 내에서 각 종류의 상대적인 수량만 알면 가장 적은 종류를 0마리로 두고 나머지 종류의 마릿수를 확정할 수 있다.

예를 들어 $(1, 3)$ 개구리가 $(2, 3)$ 개구리보다 3마리 많고, $(3, 3)$ 개구리가 $(1, 3)$ 개구리보다 5마리 적다는 정보를 갖고 있다고 하자. 세 종류의 개구리를 전부 사용한다면 $(1, 1)$ 개구리로 대체하는 것이 이득이므로, 최적의 배치에서 이 세 종류의 개구리가 전부 등장하지는 않을 것이다. 이 예시에서는 $(3, 3)$ 개구리가 가장 적다는 것을 알 수 있고, $(3, 3)$ 개구리가 한 마리도 남지 않을 때까지 대체하고 나면 $(1, 3)$ 개구리는 5마리, $(2, 3)$ 개구리는 2마리 남게 된다.

간격이 4 또는 5인 개구리 구하기

간격이 5인 개구리는 다섯 종류가 있는데, 이 다섯 종류의 개구리를 전부 사용한다면 $(1, 1)$ 개구리로 대체하는 것이 이득이다. 따라서 각 종류 사이의 상대적인 수량만 알면 각 종류의 마릿수를 확정할 수 있다.

개구리들은 항상 같은 간격으로 뛰어가므로, 어떤 간격들의 최소공배수만큼 떨어진 두 개의 칸은 그 간격들에 해당하는 개구리들을 공유한다. 따라서 $LCM(1, 2, 3, 4, 6)=12$칸 떨어져 있는 두 칸은 5를 제외한 모든 간격의 개구리를 공유한다.

• $A_{1}=(F_{1,1}+F_{1,2}+F_{1,3}+F_{1,4}+F_{1,6})+F_{1,5}$
• $A_{13}=(F_{1,1}+F_{1,2}+F_{1,3}+F_{1,4}+F_{1,6})+F_{3,5}$

따라서 두 칸의 값의 차이는 $(1, 5)$ 개구리와 $(3, 5)$ 개구리의 수의 차이와 같다. 이 과정을 4개의 쌍에 대해 적용하면 간격이 5인 개구리들 사이에 성립하는 4개의 관계식을 얻을 수 있다.

• $A_{1}-A_{13}=F_{1,5}-F_{3,5}$
• $A_{2}-A_{14}=F_{2,5}-F_{4,5}$
• $A_{3}-A_{15}=F_{3,5}-F_{5,5}$
• $A_{4}-A_{16}=F_{4,5}-F_{1,5}$

이제 간격이 5인 개구리들의 종류별 마릿수를 모두 구할 수 있게 되었다. 같은 과정을 간격이 4인 개구리에 대해서도 적용할 수 있다.

1. $(1, 4)$ 개구리와 $(3, 4)$ 개구리를 둘 다 사용한다면 $(1, 2)$ 개구리로 대체하는 것이 이득이다.
2. $LCM(1, 2, 3, 5, 6) = 30$칸 떨어져 있는 두 칸은 4를 제외한 모든 간격의 개구리를 공유한다.
3. $A_{1}-A_{31}=F_{1,4}-F_{3,4}$를 이용해 $(1, 4)$ 개구리와 $(3, 4)$ 개구리의 수를 확정할 수 있다.
4. 이 과정을 $(2, 4)$ 개구리와 $(4, 4)$ 개구리에 대해서도 적용한다.

보다시피 어떤 개구리들의 조합을 더 적은 마릿수의 조합으로 대체한다는 것은 이 문제를 푸는 데 있어 가장 강력한 아이디어이다.

나머지 간격의 개구리 구하기

아쉽게도 간격이 1, 2, 3 또는 6인 개구리는 위와 같은 방법으로 구할 수 없다. 이 중 어떤 간격을 제외하더라도 나머지 간격들의 최소공배수가 여전히 그 간격의 배수이기 때문이다. 발상의 전환이 필요한 시점인데, 이번에는 새로운 관찰을 하는 것이 아니라 출발점으로 되돌아가 볼 것이다.

문제의 본질을 되새겨 보면, 문제의 답을 구하기 위해서는 모든 관계식을 만족하는 개구리들의 배치를 모두 나열한 뒤 그 중 가장 적은 개구리를 사용하는 배치를 뽑으면 된다. 물론 여전히 모든 종류의 개구리를 아무렇게나 배치해 보기에는 경우의 수가 너무 많다. 그러나 우리는 이제 강력한 테크닉을 익혔기 때문에 관계식이 한두 개만 더 추가되어도 많은 종류의 개구리들을 추가로 결정할 수 있고, 훨씬 더 효율적으로 답의 후보를 추려낼 수 있다.

여기서 추가할 관계식은 지금까지 봐 온 관계식들과 마찬가지로 여러 $F_{a, b}$로 이뤄진 식의 값이 얼마인지를 나타낼 것이며, 이렇게 값을 임의로 정할 식을 미지수라고 부를 것이다. 풀이에서 사용하는 미지수의 개수가 적을수록 고려해야 하는 답의 후보의 수가 줄어들고, 더 빠르고 간결한 풀이를 만들 수 있다. 따라서 미지수를 효율적으로 설정하는 것이 풀이의 핵심이 된다. 좋은 미지수를 설정하기 위해서는 몇 가지 주의를 기울일 사항이 있다.

• 이미 있는 정보로 얻을 수 있는 값을 굳이 미지수로 설정할 필요는 없다. 이 경우 봐야 하는 후보의 수가 늘어날 뿐더러 풀이 과정에서 모순이 일어나 입력을 만족시킬 수 없는 배치가 나오게 된다. 이를 역으로 이용하면, 만약 풀이 과정에서 입력을 만족시킬 수 없는 배치가 나온다면 불필요한 미지수를 설정하고 있다고 볼 수 있다.
• 한 종류의 개구리의 수보다는 두 종류의 개구리의 수의 차이를 미지수로 두는 것이 좋다. 지금까지의 풀이에서 봤듯이 절대적인 값보다는 상대적인 값이 더 많은 정보를 담고 있다.

여기서는 $F_{1,2}-F_{2,2}$를 임의로 정한 뒤 나머지 값을 구해 보기로 한다. 이 값을 정하면 $F_{1,2}$와 $F_{2,2}$의 값을 결정할 수 있음은 이제 자명하게 느껴질 것이다.

이제 간격이 6인 개구리들 간의 관계식을 찾을 수 있다.

1. 간격이 2, 4 또는 5인 개구리의 수는 전부 알고 있으며, $(1, 6)$ 개구리와 $(4, 6)$ 개구리를 둘 다 사용한다면 $(1, 3)$ 개구리로 대체하는 것이 이득이다.
2. $LCM(1, 3)=3$칸 떨어져 있는 두 칸은 1과 3 간격의 개구리를 공유한다.
3. $A_{1}-A_{4} = (F_{1,2} - F_{2,2}) + (F_{1,4} - F_{4,4}) + (F_{1,5} - F_{4,5}) + (F_{1,6} - F_{4,6})$를 이용해 $(1, 6)$ 개구리와 $(4, 6)$ 개구리의 수를 확정할 수 있다.
4. 이 과정을 $A_{2} - A_{5}$, $A_{3} - A_{6}$에 대해서도 적용하면 간격이 6인 개구리들을 전부 구할 수 있다.

다음으로 $A_{1} - A_{2}$, $A_{2} - A_{3}$의 값을 통해 간격이 3인 개구리들도 구할 수 있다. 마지막으로 지금까지 얻은 값을 $A_{1}=F_{1,1}+F_{1,2}+F_{1,3}+F_{1,4}+F_{1,5}+F_{1,6}$에 대입하면 $F_{1,1}$의 값을 얻을 수 있다.

이제 모든 종류의 개구리의 수를 구했다!

정리

지금까지 $N$이 충분히 크다면 미지수를 하나 설정하여 $O(M)$개의 답의 후보를 추려낼 수 있음을 보였다. 일반적인 문제와 달리 $N$이 크면 오히려 풀기 쉬워진다는 점이 이 문제의 독특한 점이다.

$F_{2,4}$와 $F_{4,4}$의 값을 얻기 위해 $A_{2}-A_{32}$를 참조했으므로 지금까지의 풀이가 성립하는 $N$의 하한은 32이다. 32 미만의 $N$에 대해 어떻게 풀어야 할지는 여전히 막막하다.

다음 내용에서는 위의 풀이를 더욱 최적화하여 $N$의 하한을 줄여 볼 것이다. 어디까지? 모든 개구리를 사용할 수 있는 하한선인 12까지!

$N=12$

일단 간격이 4 또는 5인 개구리를 구하고 나면 나머지 간격의 개구리를 구하는 과정은 앞의 6개 항만을 참조하므로 그대로 쓸 수 있다. 따라서 저 두 간격의 개구리를 구하는 과정만 12개의 항 안에 압축시킬 수 있다면 목표를 달성할 수 있다.

간격이 4 또는 5인 개구리 구하기

두 개의 칸의 값을 비교해서 하나의 간격에 대한 관계식을 찾는 것은 불가능해졌으므로, 아쉬운 대로 두 개의 간격에 대한 관계식이라도 구해 보자. $LCM(1, 2, 3, 6)=6$칸 떨어져 있는 두 칸을 비교하면 나머지 간격들을 전부 소거할 수 있다.

• $A_{1}-A_{7}=(F_{1,4}-F_{3,4})+(F_{1,5}-F_{2,5})$
• $A_{2}-A_{8}=(F_{2,4}-F_{4,4})+(F_{2,5}-F_{3,5})$
• $A_{3}-A_{9}=(F_{3,4}-F_{1,4})+(F_{3,5}-F_{4,5})$
• $A_{4}-A_{10}=(F_{4,4}-F_{2,4})+(F_{4,5}-F_{5,5})$
• $A_{5}-A_{11}=(F_{1,4}-F_{3,4})+(F_{5,5}-F_{1,5})$
• $A_{6}-A_{12}=(F_{2,4}-F_{4,4})+(F_{1,5}-F_{2,5})$

여기서 연속한 4개의 식을 더하면 간격이 4인 개구리가 전부 소거되고 간격이 5인 개구리 두 종류에 대한 관계식을 찾을 수 있다. 이는 간격 4와 5가 1 차이이기 때문에 성립하는 기막힌 우연이다!

• $A_{1}+A_{2}+A_{3}+A_{4}-A_{7}-A_{8}-A_{9}-A_{10}=F_{1,5}-F_{5,5}$
• $A_{2}+A_{3}+A_{4}+A_{5}-A_{8}-A_{9}-A_{10}-A_{11}=F_{2,5}-F_{1,5}$
• $A_{3}+A_{4}+A_{5}+A_{6}-A_{9}-A_{10}-A_{11}-A_{12}=F_{3,5}-F_{2,5}$

이제 나머지 관계식들을 찾는 것은 식은 죽 먹기이다.

• $A_{5}-A_{11}=(F_{1,4}-F_{3,4})+(F_{5,5}-F_{1,5})$ → $F_{1,4}-F_{3,4}$ 계산
• $A_{6}-A_{12}=(F_{2,4}-F_{4,4})+(F_{1,5}-F_{2,5})$ → $F_{2,4}-F_{4,4}$ 계산
• $A_{4}-A_{10}=(F_{4,4}-F_{2,4})+(F_{4,5}-F_{5,5})$ → $F_{4,5}-F_{5,5}$ 계산

필요한 모든 관계식을 찾았으니 이제 간격이 4 또는 5인 개구리를 전부 구할 수 있다. 따라서 $N$의 하한을 12까지 줄이는 데 성공했다!

더 작은 $N$에 대해서

이전의 풀이를 더욱 최적화하여 모든 개구리를 사용할 수 있다면, 즉 $N \geq 12$라면 $O(M)$에 문제를 풀 수 있음을 보였다. 이제 문제를 거의 다 해결한 것처럼 느껴진다.

그러나 이 아래로는 $N$이 하나씩 작아질 때마다 문제가 완전히 달라지는 절망적인 상황이 펼쳐진다. 예를 들어 $N=11$일 경우 $(6, 6)$ 개구리가 한 칸만 밟고 나가게 되기 때문에 더 이상 사용할 수 없게 되고, $F_{6,6}$ 또는 $A_{6}$을 참조했던 기존의 풀이는 못 쓰게 되어 버린다.

안타깝게도 본인은 이 상황을 그다지 아름답게 극복하지 못했고, 2부터 11까지의 모든 $N$에 대해 각각 다른 풀이를 찾아서 해결했다. 이 과정은 다소 피곤했지만 어떤 개구리를 사용할 수 없게 됨으로써 기존의 규칙이 깨지고, 대신 새로운 규칙이 생겨나는 것을 지켜보는 것은 굉장히 재미있었다.

예시로 $N=9$일 때의 풀이 과정을 서술해 보도록 한다.

예시($N=9$)

칸이 9개밖에 없다면 $(5, 5)$, $(4, 6)$, $(5, 6)$, $(6, 6)$ 개구리를 더 이상 사용할 수 없다. 따라서 각 칸에 대한 수식은 다음과 같다.

• $A_{1}=F_{1,1}+F_{1,2}+F_{1,3}+F_{1,4}+F_{1,5}+F_{1,6}$
• $A_{2}=F_{1,1}+F_{2,2}+F_{2,3}+F_{2,4}+F_{2,5}+F_{2,6}$
• $A_{3}=F_{1,1}+F_{1,2}+F_{3,3}+F_{3,4}+F_{3,5}+F_{3,6}$
• $A_{4}=F_{1,1}+F_{2,2}+F_{1,3}+F_{4,4}+F_{4,5}$
• $A_{5}=F_{1,1}+F_{1,2}+F_{2,3}+F_{1,4}$
• $A_{6}=F_{1,1}+F_{2,2}+F_{3,3}+F_{2,4}+F_{1,5}$
• $A_{7}=F_{1,1}+F_{1,2}+F_{1,3}+F_{3,4}+F_{2,5}+F_{1,6}$
• $A_{8}=F_{1,1}+F_{2,2}+F_{2,3}+F_{4,4}+F_{3,5}+F_{2,6}$
• $A_{9}=F_{1,1}+F_{1,2}+F_{3,3}+F_{1,4}+F_{4,5}+F_{3,6}$

간격이 4 또는 5인 개구리만 남기는 것은 여전히 강력한 접근이다. 이번에도 적용해 보도록 하자.

• $A_{1}-A_{7}=(F_{1,4}-F_{3,4})+(F_{1,5}-F_{2,5})$
• $A_{2}-A_{8}=(F_{2,4}-F_{4,4})+(F_{2,5}-F_{3,5})$
• $A_{3}-A_{9}=(F_{3,4}-F_{1,4})+(F_{3,5}-F_{4,5})$

그러나 이번에는 식이 3개밖에 나오지 않아서 간격이 4인 개구리들을 소거할 수 없다. 좋은 방법이 보이지 않으니 $F_{1,4}-F_{3,4}$, $F_{2,4}-F_{4,4}$ 두 개의 값을 임의로 정해 놓고 풀이를 진행해 보도록 하자.

• $A_{1}-A_{7}=(F_{1,4}-F_{3,4})+(F_{1,5}-F_{2,5})$ → $F_{1,5}-F_{2,5}$ 계산
• $A_{2}-A_{8}=(F_{2,4}-F_{4,4})+(F_{2,5}-F_{3,5})$ → $F_{2,5}-F_{3,5}$ 계산
• $A_{3}-A_{9}=(F_{3,4}-F_{1,4})+(F_{3,5}-F_{4,5})$ → $F_{3,5}-F_{4,5}$ 계산

이제 간격 5인 개구리들 간의 모든 관계식을 얻었다. 그러나 이번에는 $(5, 5)$ 개구리가 없기 때문에 이 개구리들을 모아서 $(1, 1)$ 개구리로 대체하는 것이 불가능하다. 문제가 바뀌었으니 규칙도 새로 찾아야 하는 것이 당연한 일. 다시 열심히 관찰해 보면 이번에도 대체재를 찾을 수 있다!

따라서 비록 미지수가 두 개 추가되었지만 이번에도 간격이 4 또는 5인 개구리들을 전부 구할 수 있게 되었다. 나머지 개구리들은 여전히 $F_{1,2}-F_{2,2}$를 임의로 정하면 어렵지 않게 구할 수 있다.

결론

지금까지 $N \geq 12$인 경우에 대해 $O(M)$ 풀이를 찾는 과정과 $N < 12$인 경우의 예시 하나를 소개했다. 예시로 든 $N=9$는 본인의 풀이 중 가장 많은 미지수를 사용하는 경우이며, 따라서 풀이의 전체 시간복잡도는 $O(M^{3})$이다.

이 풀이를 읽는 분들도 풀이의 나머지 부분을 직접 채우고 풀이를 찾아 나가는 즐거움과 맞았습니다!!를 받는 기쁨을 모두 얻을 수 있기를 바란다. 유감스럽게도 구현 과정은 그다지 유쾌하지 않으며 대단히 많은 테스트를 해야 할 것이므로, 데이터를 생성하고 답을 확인하는 프로그램을 같이 만들어 두는 것을 권장한다.

다른 분과 이 문제에 대해 대화를 나누다 1994년 국제정보올림피아드 문제인 The Buses를 소개받았다. 이 문제는 일부 제약 조건이 다르지만 기본적으로 청개구리 문제와 같은 내용을 담고 있으며, 굉장히 오래된 문제인 만큼 의도된 풀이 역시 최근의 알고리즘 문제와는 완전히 동떨어져 있다.

The technique is sometimes called branch-and-bound.

10여 년 전까지만 해도 이처럼 주어진 시간 내에 올바른 답이 나온다는 것이 보장되지 않는 가지치기 또는 최적화 알고리즘을 다루는 문제가 전 세계의 프로그래밍 대회에서 흔하게 출제되었다.³ 개인적으로는 청개구리 문제 역시 적절한 우선순위에 따라 가지치기를 하는 완전 탐색이 의도된 해법이었을 것으로 추측한다.⁴