백준 10837번 동전 게임 :: 마이구미

이 글은 백준 알고리즘 문제 10837번 "동전 게임" 을 다뤄본다.

정올(KOI) 중등부, 고등부 출제 문제이다.

규칙을 찾아 단순한 구현을 통해 해결할 수 있다.

문제 링크 - https://www.acmicpc.net/problem/10837

영희와 동수는 동전 던지기 게임을 하고 있다. 이 게임은 K번 라운드로 구성되고 다음과 같은 규칙들을 따른다:

1. 한 라운드에서 영희와 동수는 한 번씩 동전을 던지고 항상 영희가 먼저 던진다. 
2. 동전을 던져 앞면이 나오면 1점을 얻고, 뒷면이 나오면 점수를 얻지 못한다. 
3. 한 명이 남은 기회에 모든 점수를 얻더라도 상대방이 현재까지 얻은 점수보다 작게 되면 게임 도중 어떤 시점에서도 게임은 바로 끝난다. 

위 표에서 영희와 동수의 점수가 0과 2가 되는 것이 불가능한 이유는 두 번째 라운드에서 영희가 뒷면이 나와서 점수를 얻지 못하는 순간 게임의 규칙 3에 의해서 0과 1로 게임이 끝나기 때문이다. 

0이상 K이하인 정수 M과 N이 주어질 때, 이 두 정수가 각각 영희와 동수의 점수가 될 수 있는지 여부를 판별하는 프로그램을 작성하시오.

문제는 비교적 쉽게 이해할 수 있고, 문제의 핵심은 항상 영희가 먼저 던지는 것과 규칙 3번이다.

문제에서 나타나는 표의 (0, 2) , (2, 0) 를 비교하면 문제가 원하는 것이 무엇인지 쉽게 추측할 수 있다.

M = 0, N = 2
=> (0, 1) 에서 2라운드에서도 점수를 못 얻으면 동수보다 점수가 커질 수 없다.

M = 2, N = 0
=> (1, 0) 에서 영희가 먼저 던지기 때문에 가능.

여기서 추측할 수 있는 건, 위와 같이 M < N, M > N 두 가지 경우 결과가 다르다는 것을 알 수 있다.

그리고 쉽게 알 수 있는 건 M, N 이 같다면, 라운드에 상관없이 점수가 될 확률은 100% 이다.

점수가 될 가능성에 대해서는 M == N, M < N, M > N 3가지로 볼 수 있다.

각 경우의 가능성을 위해 본인은 M 과 N 사이의 차이(gap)와 남은 라운드 수를 이용했다.

어떤 두 수가 주어질 때, 남은 라운드 수가 두 수간의 차이를 메울 수 있다는 건 점수가 가능하다는 의미가 되기 때문이다.

영희가 먼저 던지기 때문에, 영희에게 1을 더 줄 수 있다. 

문제를 이해했고, 본인이 말하고자하는 것을 이해했다면, 코드를 통해 이해할 수 있을 것이다.

Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2015/10837.java

private void solve() {
    int n = sc.nextInt();
    int c = sc.nextInt();
    StringBuilder sb = new StringBuilder();
 
    while (c-- > 0) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int gap = Math.abs(a - b);
        int remain = n - Math.max(a, b);
 
        if (a == b) {
            sb.append("1\n");
        } else if (a < b) {
            if (gap - remain <= 1) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        } else {
            if (gap - remain <= 2) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }
    }
    System.out.println(sb.toString());
}