원글 링크:

https://gall.dcinside.com/mgallery/board/view/?id=github&no=28912&page=1


여느 문제가 그렇듯 알면 쉽고 모르면 어려운 문제임.

이하 풀이 들어감. 근데 존나 두서없음.

S나 P가 어딘가 나사가 빠졌거나 누가 거짓말을 했거나 하는 일은 없다고 가정.

편의를 위해 두 사람은 문제에서처럼 각각 S와 P, 각각이 가진 단서 수는 각각 s와 p,

그리고 처음 주어진 두 자연수의 값은 n과 m이라고 하겠음(크기는 고려X).




0. 2와 50 사이의 소수 리스트


2, 3, 5, 7, 11, 13, 17, 19, 23 // 29, 31, 37, 41, 43, 47

갤럼들 읽으면서 참고하라고 써둠.

(여기서 23과 29 사이를 구분해둔 데에는 이유가 있음. 바로 아래 1-(1) 참조.)




1. P가 답을 모른다는 걸 S가 아는 것의 의미


일단 S는 반드시 "P가 답을 확실하게 모른다"는 걸 알거나 "P가 답을 알 수도 있다"는걸 아는 두 상태 중 하나.

P가 자기 단서만으로 답을 알 수도 있다는걸 S가 안다면 그게 어떤 경우일지 생각해보면 대충 3가지로 좁혀지는데,


(1) s가 좀 클 때; 정확히는 s >= 31일 때.

s >= 31 = 2 + 29이면, s = n + m으로 분할했을 때 둘 중 하나가 29일 가능성이 발생해버림.

실제로 (??, 29)가 그 자연수 쌍이었으면 P는 대화하기도 전에 그걸 알았을 것.

※ 위에서 말한 소수 리스트에서 23과 29 사이를 갈라둔 이유가 여기에 있음.

예를 들어서 s = 27이라고 하면 s - 2 = 25보다 작은 가장 큰 소수가 끽해야 23인데,

이것만으로는 P가 알고 있는 (n, m)쌍이 (4, 23)일지 (2, 46)일지 모름.

즉 29는 자기 자신의 2배가 n과 m의 상한인 50보다 커지는 가장 작은 소수이며,

s가 29+2보다 크다면 n과 m의 후보로 29가 발생해버리고

이 시점에서 P가 n과 m 중 하나를 29로 특정할 수 있게 돼버리는 가능성이 있는 거기 때문에

s >= 31은 불가능, 즉 s < 30.


(2) s가 극단적으로 작을 때; 정확히는 s <= 6일 때.

s = 4) (n, m) = (2, 2). S든 P든 대화고 뭐고 바로 깨닫는 조합.

s = 5) (n, m) = (2, 3). s = 4일 때와 동일.

s = 6) (n, m) = (2, 4) or (3, 3). 어느 쪽이든 S는 "P가 답을 알 수도 있다" 이상으로

"P는 무조건 답을 알고 있다"는 걸 알기 때문에 이 가능성도 배제.


(3) s가 소수 2개의 합으로 나타낼 수 있을 때.

예컨대 s = 16이었다고 할 때 n과 m의 조합 중 (3, 13)이나 (5, 11) 같은 걸 생각해보면

p = 39이거나 55일 수 있다는 거임.

그런데 실제로 p가 39거나 55거나 하면 P는 그것만으로 n과 m의 값을 유추할 수 있게 됨.

1이 아닌 두 자연수의 곱 중 쟤네들이 나오는 조합이 각각 그 소수 둘, 즉 (3, 13)과 (5, 11)밖에 없으니까.

요컨대 s를 2 이상인 두 자연수의 합으로 분할했을 때 두 수 모두 소수인 경우가 있으면,

p의 값이 두 소수끼리의 곱일 수 있다는 얘기가 되고

그러면 P가 자신의 단서만으로 답을 알 수도 있다는 얘기가 됨.

이걸 S도 알 테니, 즉 S의 첫 번째 대사에 모순.


위까지의 과정에서, (1)에서는 s >= 31, (2)에서는 s <= 6이 불가능하다는 걸 알았음.

(3)은 s가 소수 2개의 합으로 분할되는지를 살펴보면 되는데, 7 <= s <= 30인 범위만 살펴보면 쉽게 구해진다.

7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 24, 25, 26, 28, 30인데,

얘네들을 소수 2개의 합으로 나타내는 방법은 갤럼들이 직접 찾아보길.


이것만으로 s가 가질 수 있는 값의 가능성은 정확하게 5가지, 즉 11, 17, 23, 27, 29로 좁혀짐.

이제 이 대사를 들은 P쪽으로 관점을 바꿔보자.




2. S의 말을 듣고도 아직 답을 모르는 P


S의 첫 번째 대사 "P가 답을 모른다는 건 알겠네"에서 P도 위 결론까진 도달했음.

즉 s가 11, 17, 23, 27, 29 중 하나인 건 알았다는 얘기.

이걸 듣고도 모른다는 건, p를 곱 n * m으로 분해할 수 있는 모든 가능성을 따져봤을 때

n + m으로 가능한 값이 이 5개 수 중 둘 이상이 있다는 뜻이 됨.


이해를 돕기 위해 과이썬으로 값을 모조리 계산해봤다.


>>> [[n*(s-n) for n in range(2, (s+1)//2)] for s in [11, 17, 23, 27, 29]]


위에서 구한 5가지 s마다 가능한 p의 값들을 모조리 구하는 건데,

보기 쉽게 나열하면 이런 느낌.


(s -> list of possible p's)

11 -> [18, 24, 28, 30]

17 -> [30, 42, 52, 60, 66, 70, 72]

23 -> [42, 60, 76, 90, 102, 112, 120, 126, 130, 132]

27 -> [50, 72, 92, 110, 126, 140, 152, 162, 170, 176, 180, 182]

29 -> [54, 78, 100, 120, 138, 154, 168, 180, 190, 198, 204, 208, 210]


예를 들어서 P가 가진 단서가 p = 162라고 해보자.

이 값은 s = 27일 때밖에 얻어지지 않는 값으로, (n, m) = (9, 18)가 유일한 가능성.

즉 S의 대사를 듣고 s의 후보군 11, 17, 23, 27, 29을 찾아내는 데에 성공하면,

p = 162라는 사실로부터 바로 s = 27인 걸 추리해내고

"아니, 난 (너 말 듣고) 알았어" 라는 식으로 이야기했을 거임.

역으로 P의 대사가 "그래, 도저히 모르겠다"였다는 건 위 리스트에 있는 수에서

p가 두 번 이상 등장한다는 걸 의미함.

예를 들면 p = 42면 s = 17과 s = 23의 두 가지 가능성이 존재하고, 각각

(n, m) = (3, 14) 및 (n, m) = (2, 21).

이런 p의 값과 그에 상응하는 가능한 s의 후보를 찾으면 이런 느낌이다.


(p <- list of possible s's)

30 <- [11, 17]

42 <- [17, 23]

60 <- [17, 23]

72 <- [17, 27]

120 <- [23, 29]

126 <- [23, 27]

180 <- [27, 29]


이걸로 p가 가질 수 있는 값의 가능성은 30, 42, 60, 72, 120, 126, 180의 7가지로 줄였음.

P의 생각은 이걸로 다 들여다봤으니, 이제 다시 S 머릿속으로 들어가보자.




3. 줄일 데까지 줄인 가능성; S가 알면 우리 모두 안다


S는 단서 수로 s = 11, 17, 23, 27, 29의 수 중 하나를 이미 가지고 있고,

방금까지의 대화로 p의 가능성까지 모두 알게 됐음.

여기서 위 표를 잘 보고 다시 p와 s의 대응을 뒤집어보면 아래와 같음.


(s -> list of possible p's)

11 -> [30]

17 -> [30, 42, 60, 72]

23 -> [42, 60, 120, 126]

27 -> [72, 126, 180]

29 -> [120, 180]


만약에 여기까지의 대화로도 S가 답을 알 수 없었다면,

그건 p값들 중에서 자기가 가지고 있는 s값과 호응이 되는(즉 n + m == s, n * m == p인) 값이

2개 이상 존재한다는 말이 됨. 즉 s = 17, 23, 27, 29 중 하나였다는 뜻.

그런데 S가 답을 알아버렸다네?

그럼 p의 후보가 하나밖에 없는 s값인 11이 S가 가지고 있었던 단서가 되고,

P는 그 11에 대응되는 유일한 p 후보값인 30을 단서로 갖고 있었던게 됨.

즉 s = 11, p = 30으로, 위 과정을 되짚어가든 2차방정식을 풀든 처음 두 자연수의 값을 찾으면

(n, m) = (5, 6)임을 얻는다.

(이 뒤에 오는 P의 대사 "나도 답을 알았어"에 큰 의미는 없음.

애초에 P는 우리보다 정보가 더 많았으면 많았지 적지는 않았으니까.

우리가 아는 시점에는 P도 당연히 정답이 (5, 6)임을 알아야 하는 거.)


◆




손으로 풀려면 풀 수야 있겠는데,

보다시피 두 번째 대사에서 계산할 게 많아서 그냥 컴퓨터 썼음.

질문?