백준 30506: 가위 가위 가위

🧭 문제 분석

가위바위보 머신과 대결을 한다.
한 번의 대결에 머신과 100번의 가위바위보를 하는데, 머신에게 몇번을 이겼는지만 알 수 있다.
맨 처음 대결에 모두 가위를 내는 것으로 시작하여,
100번의 대결을 추가로 진행하고 머신이 내고 있는 고정된 100번의 가위바위보 패턴을 알아내야 한다.

✅ 문제 풀이

그냥 경우의 수를 따져보는 문제인 줄 알았는데, 알고리즘 유형을 보니 차분 공격이었다

차분 공격이란, 암호 해독에 사용되는 방법으로, 이전에 입력한 암호의 결과와 새롭게 입력한 암호의 결과를 비교하여 암호를 해독하는 방식이라고 한다.

그것에 기반하여 다시 문제를 보면, 머신이 갖고 있는 가위바위보 패턴은 암호라고 할 수 있다.

우선 가장 첫번째 대결에 모두 가위를 내고, 이긴 값을 돌려 받게 된다. (이 조건이 없었다면 문제가 더 어려워 졌을 것 같음)

이제 100번의 대결을 더 진행하면서 우리가 확인해볼 것은, 이전에 입력한 암호의 결과(모두 가위를 냈을 때)와 새롭게 입력한 암호(가위 대신 바위 혹은 보를 내보는 것)이다.

가위 대신 바위를 내본다고 하자.

만약 이긴 값이 늘어났다면, 그 판은 바위를 내야 이기는 것이다.
만약 이긴 값이 줄어들었다면, 그 판은 원래대로 했어야 이기는 것이다. (가위)
만약 이긴 값에 변동이 없다면, 그 판은 바위를 내도 지고, 가위를 내도 지는 것이다. (보)

이것을 기반으로 100번의 대결을 더 진행하면, 결국 각 가위바위보에 무엇을 내야 이기는 지 알 수 있고, 그 패턴의 정반대가 머신의 패턴이다.

이 논리를 기반으로 간단하게 코드를 작성하면 정답이다

fun main() {
    // 처음에 다 가위냈을 때의 결과 K
    var K = readln().toInt()
    // 처음에 다 가위낸 상태로 시작
    val RSP = "2".repeat(100).toCharArray()
    // 여기에 머신의 패턴을 기록한다
    val answer = StringBuilder()
    repeat(100) {
        // 가위대신 바위내기
        RSP[it] = '0'
        // 결과 확인
        println("? ${RSP.joinToString("")}")
        System.out.flush()
        val result = readln().toInt()

        // 값이 증가 -> 바위로 이길 수 있음 (머신은 가위를 냈음)
        // 값 유지 -> 보로 이길 수 있음 (머신은 바위를 냈음)
        // 값이 감소 -> 가위로 이길 수 있음 (머신은 보를 냈음)
        when(result) {
            K + 1 -> {
                answer.append('2')
                K++
            }
            K -> {
                RSP[it] = '5'
                answer.append('0')
                K++
            }
            K - 1 -> {
                RSP[it] = '2'
                answer.append('5')
            }
        }
    }
    println("! $answer")
    System.out.flush()
}