[Python] 30924번 A+B - 10 (제2편)

https://www.acmicpc.net/problem/30924

30924번: A+B - 10 (제2편)

---

 

23/12/19

 

 

무작위화 알고리즘을 사용하는 아주 좋은 문제여서, 소개해보고자 한다.

---

 

문제 접근 방식:

 

 

문제는 아주 간단하다.

 

이 문제에서는 총 $19,997$번의 질의를 할 수 있으며, 가능한 $A$와 $B$의 범위는 $1$부터 $10,000$까지이기 때문에 확정적으로 $A$와 $B$를 결정짓기 위해서는 $19,998$번의 질의가 필요하다.

 

왜냐하면, $A$를 알아내기 위해 $9,999$번 물어보고, $B$를 알아내기 위해 $9,999$번 물어봐야 결정지어지기 때문이다.

 

근데 문제는 $19,997$번 밖에 질의를 하지 못한다.

 

이 경우에서, 우리는 무작위화 알고리즘을 활용할 수 있다.

 

랜덤 함수를 활용하여 무작위로 숫자를 물어보자. 이 숫자가 만약 $A$와 맞지 않다면, 이미 불렀던 숫자를 제외한 숫자를 물어보자.

 

만약 이 숫자가 $A$와 맞다면 그 숫자를 $A$라고 하고, $B$를 물어보자.

 

실제로 이 과정을 코드로 짜보면 $A$를 알아내는데 $9,999$번 질의를 하는 확률은 극히 극히 낮다.

 

계산을 해보자. 먼저 $1$부터 $10,000$까지의 숫자 중 무작위로 숫자를 던져서 맞추지 못할 확률은 $9999/10000$이다.

 

이후에는 숫자가 하나 빠지므로, $9998/9999$가 될 것이다.

 

이를 반복하여 모든 확률을 곱하면 $9,999$번 질의를 해도 전부 맞추지 못할 확률은 $1/10000$밖에 되지 못한다. 즉, $0.01$%밖에 되지 않는다.

 

코드를 만 번 돌려도 $1$번 정도 나오는 아주 낮은 확률이다.

 

우리는 $B$까지 알아 내야하는데, 이에 따르면 $19,997$번의 질의 기회를 모두 다 써버려도 알아내지 못할 확률은 $1/10000 \times 1/10000$가 되어버린다.

 

 이는 $0.000001$%로, 로또 당첨 확률보다 낮다.

 

그러니 이런 식으로 "확정적"으로 답이 나오지 않는 방식이라고 할지라도 답이 나오지 않는 확률이 극히 낮을 경우, 무작위화 알고리즘으로 접근해 볼 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

from random import shuffle
num_li = list(range(1, 10001))
shuffle(num_li)
while True:
    A = num_li.pop()
    print(f'? A {A}', flush = True)
    k = int(input())
    if k == 1:
        break
num_li = list(range(1, 10001))
shuffle(num_li)
while True:
    B = num_li.pop()
    print(f'? B {B}', flush = True)
    k = int(input())
    if k == 1:
        break
print(f'! {A+B}', flush = True)