• 백준 10837번 동전 게임 :: 마이구미
    알고리즘 풀이/수학 2018. 4. 1. 21:46
    반응형

    이 글은 백준 알고리즘 문제 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



    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    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());
    }
    cs


    반응형

    댓글 0

Designed by Tistory.