[BOJ] 25487번 단순한 문제 (Large)

[BOJ] 25487번 단순한 문제 (Large) 문제

굉장히 흥미로웠던 정수론 문제였다. 물론 25494번 단순한 문제 (Small) 문제도 있지만 그 문제는 브루트 포스로도 풀리며, 당연히 여기서 작성하는 정답을 사용해도 풀린다.

---

사실 이 문제는 코드만 보면 한없이 쉬운 문제다. 이 문제의 핵심은 "왜 그렇게 풀 수 있는가?" 이다.

먼저 주어진 조건을 여기서 나열해보자.

• $ 1 \leq x \leq a $
• $ 1 \leq y \leq b $
• $ 1 \leq z \leq c $
• $ (x \; mod \; y) = (y \; mod \; z) = (z \; mod \; x) $

여기서 $ (A \; mod \; B) $는 $ A\: $를 $ B\: $로 나눈 나머지를 의미하고, $ a $, $ b $, $ c \: $는 입력으로 들어오는 수다.

위의 조건이 주어졌을 때 만족하는 정수 쌍 $ (x, \; y, \; z) $의 개수를 구하는 것이 문제다.

이 문제를 만났을 때 우리가 풀어야 하는 부분은 "어떤 경우일 때가 정답인가?" 이다. 정답은 반드시 존재하는 경우에만 문제로 만들어지기 때문에 정답이 존재하는 이유는 굳이 증명하지 않아도 된다. 다만 여기는 내가 하고 싶은 말을 하고 싶은 곳이니 정답이 존재하는 이유도 같이 기술할 것이다.

---

1. 해가 존재하는가?

이를 증명하는 방법은 간단하다. 귀류법(Proof by contradiction, 결론을 부정한 명제에서 얻는 모순을 통해 기존 명제가 참임을 증명하는 방법)을 이용하면 된다.

이를 위해 위의 조건이 주어졌을 때 만족하는 정수 쌍 $ (x, \; y, \; z) $가 없다고 가정해보자. 하지만 (약간의 스포를 곁들여) $ x=y=z \: $인 경우에 이 명제는 모순이 되어버리기 때문에 해가 존재한다.

---

2. 왜 $ x=y=z \: $인 경우가 답이 되는가?

일단 $ (x \; mod \; y) = (y \; mod \; z) = (z \; mod \; x) = k \: $라고 하자. 아래와 같이 풀어서 써볼 수 있다.

• $ (x \; mod \; y) = k $
• $ (y \; mod \; z) = k $
• $ (z \; mod \; x) = k $

나머지 연산의 정의를 잘 생각해본다면 순서대로 $ k < y,\; k < z,\; k < x\: $를 만족한다. 이 부등식을 적절히 적용해보자.

• $ (x \; mod \; y) < x $
• $ (y \; mod \; z) < y $
• $ (z \; mod \; x) < z $

위의 부등식에서 또한 나머지 연산의 정의를 응용하면 아래의 수식으로 바꿀 수 있다.

• $ x \geq y $
• $ y \geq z $
• $ z \geq x $

즉, $ x \geq y \geq z \geq x $가 되어버리며, 이를 만족하는 경우는 $ x=y=z $ 뿐이다.

따라서 이 문제에서의 정답인 정수 쌍 $ (x, \; y, \; z) $의 개수는 $ min(a, \; b, \; c) $가 된다.

---

정작 내가 이 문제의 답을 알아챈 방식은 굉장히 직관에 의존했다.

$ x \: $를 $ k \: $, $ y \: $를 $ k+1 \: $등으로 두면서 범위를 좁혀나갔고, 결국에는 $ x=y=z \: $일 때에만 정답이 존재할 것 같다는 직관이 서게 되었다. 다행히 이 직관은 정답이었다.

---

여기에 약간의 사족을 곁들이고 싶다. 수학 문제에서의 직관은 때때로 잘못된 정답을 가져오기도 한다. 대표적인 예시가 몬티 홀 문제다. 인터넷 커뮤니티에 한 번이라도 올라가는 순간 병림픽이 펼쳐지는 대단한 문제다.

몬티 홀 문제는 엄청 유명해서 스타크래프트 맵 컨셉으로도 사용되었고 명경기들이 많이 나오기도 했다

몬티 홀 문제 자체는 굉장히 간단하다.

• 먼저 문이 세 개가 있고, 한 개의 문 뒤에는 경품인 자동차가, 나머지 두 개의 문 뒤에는 꽝인 염소가 있다.
• 처음에는 모든 문이 닫혀있고, 참가자는 세 개의 문 중 하나의 문을 선택한다.
• 자동차의 위치를 아는 진행자는 남은 두 개의 문 중 염소가 있는 문을 연다.
• 참가자는 처음에 고른 문을 그대로 쥐고 갈지, 아니면 아직 열리지 않은 문을 열지 선택해야 한다.

언뜻 보면 당첨 확률이 1/3에서 1/2로 바뀐 것처럼 보일 테지만, 놀랍게도 조건부 확률로 인해 문을 바꿔서 자동차를 얻을 확률이 2/3으로 늘어나게 된다! 이는 사람의 일반적인 직관에 정면으로 배반하는 결과다.

조금 더 쉽게 이해하고 싶다면 이걸 보자

적절한 직관이 더 나은 결과를 불러오는 경우도 있다. 하지만 너무 직관에만 의존하면 그것 또한 문제가 되기 때문에 우리는 직관에 대해 조금 더 주의해야 할 필요가 있다.

---

정답 코드는 아래와 같다. 정답을 유도하는 과정이 더 중요하고, 코드 자체는 쉽기에 코드에 대한 설명은 생략한다.

import sys

if __name__ == '__main__':
    for T in range(int(sys.stdin.readline().rstrip())):
        print(min(list(map(int, sys.stdin.readline().rstrip().split()))))