[Python] 30506번 가위 가위 가위

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

30506번: 가위 가위 가위

---

 

23/11/16

 

 

난생 처음 보는 알고리즘 태그로, 차분 공격이라는 알고리즘 기법을 사용하는 문제다.

 

차분 공격에 대한 내용은 별거 없고, 입력값에 따라 출력값이 미묘하게 변하는 것을 이용한 암호학에서의 기법이다.

 

자세한 내용은 아래 링크를 참조하자.

 

https://en.wikipedia.org/wiki/Differential_cryptanalysis

Differential cryptanalysis - Wikipedia

---

 

문제 접근 방식:

 

 

사실 문제에서 요구하고자 하는 것은 저런 거창한 암호 해석을 요구하는 것이 아니다.

 

문제의 접근 방법은 다음과 같다.

 

처음에는 모든 판에서 가위로 냄을 알고 있다.

 

따라서, 처음의 상태에서 특정 판만 주먹으로 냈다고 생각해 보자. 그 판을 $N$번째 판이라고 하자.

 

$N$번째 판에서만 주먹을 내고 나머지 판에서는 전부 가위를 냈다면, 우리는 그에 대한 응답으로 특정 결과를 얻을 수 있다.

 

만약 기존 결과보다 바뀐 결과가 이긴 횟수가 더 많다면, 그 라운드는 내가 주먹으로 바꿨기 때문에 이긴 횟수가 늘어난 것이다.

 

즉, 기계는 그 라운드에 가위를 냈다고 추정할 수 있다.

 

만약 기존 결과보다 바뀐 결과가 이긴 횟수가 더 적어졌다면, 그 라운드는 내가 주먹으로 바꿨기 때문에 이긴 횟수가 줄어든 것이다.

 

즉, 기계는 그 라운드에 보를 냈다고 추정할 수 있다.

 

만약 기존 결과와 바뀐 결과가 이긴 횟수가 동일하다면, 그 라운드는 내가 주먹으로 내든지, 가위로 내든지 이기는 횟수에는 전혀 지장이 없다.

 

즉, 기계는 그 라운드에 주먹을 냈다고 추정할 수 있다.

 

따라서, 우리는 기존에 전부 가위로 낸 모습에서 특정 라운드만 주먹으로 바꾼 모습에 대한 응답을 얻어냄으로써, 그 라운드에 대해 기계가 어떤 것을 냈는지 알아낼 수 있는 것이다.

 

이를 토대로 구현을 하면 맞았습니다를 받을 수 있다.

 

주의할 점은, 이 문제는 다른 문제들과는 다르게 인터렉티브 문제이기 때문에 입출력을 조심해야 한다.

---

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

# 30506번 가위 가위 가위
# 차분 공격
'''
접근 방법:
하나씩 바꿔가며 접근
처음엔 전부다 가위로 시작(2로만 이루어진 문자열)
맨 앞부터 확인하며 2를 0으로 바꿔봄(가위를 주먹으로 내봄)
만약 이긴 횟수가 늘어나면 그 라운드는 기계가 가위를 냈다는 뜻임(가만히 두자)
이긴 횟수가 줄어들면 그 라운드는 원래 가위를 내서 이기는건데(기계가 보)
주먹으로 바꿔서 이긴 횟수가 줄어드는 거임 -> 가위로 냅두자.
이긴 횟수가 변하지 않으면 그 라운드는 기계가 주먹을 냈다는거임
-> 그 라운드는 보임
'''
import sys

total_hand = ''
machine_hand = ''
K = int(input())
sys.stdout.flush()
for i in range(100):
    hand = '2'*i + '0' + '2'*(99-i)
    print('?'+ ' ' + hand)
    sys.stdout.flush()
    win = int(input())
    if win > K:
        machine_hand += '2'
    elif win == K:
        machine_hand += '0'
    else:
        machine_hand += '5'
print('!'+ ' ' + machine_hand)
sys.stdout.flush()