백준 4370번: 곱셈 게임

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

4370번: 곱셈 게임

백준과 동혁이 항상 최적의 플레이를 하므로, 둘이 사용하는 수는 항상 2와 9뿐이다. 또 여기서 최적의 플레이란, 이기는 사람은 항상 수를 크게 만들고 지는 사람은 항상 수를 최소로 만드는 것이므로, 백준과 동혁이 한 턴씩 번갈아 p에 수를 곱했을 때 나오는 수는 p * 18이고 시작하는 수는 반드시 1이므로 백준과 동혁이 k번씩 수를 곱했다면 나오는 수는 18 ^ k이다.

주어진 수 n이 백준이 이기는 경우라고 가정하면 백준은 반드시 9를 곱할 것이므로 n은 18 ^ k 초과 9 * 18 ^ k 이하이고, n이 동혁이 이기는 경우라고 가정하면 백준은 반드시 2를, 동혁은 9를 곱할 것이므로 n은 9 * 18 ^ k 초과 18 ^ (k + 1) 이하일 것이다. 따라서 설명한 과정대로 p를 곱해나가면 p가 n보다 크거나 같아지는 순간 답을 알아낼 수 있다.

#include <cstdio>

int main() {
    // 동혁이 이긴다면 true, 백준이 이긴다면 false
    bool i;
    // n: 곱셈으로 만들 수, p: 최적의 플레이로 계산한 수
    unsigned int n, p, mul[2] = { 9, 2 };
    // n을 입력받은 뒤 숫자가 입력됐다면 1부터
    while ((p = scanf("%d", &n)) != EOF) {
        // k에 9와 2를 번갈아서 곱하면서 마지막으로 곱한 수가 9인지 2인지를 i에 저장
        for (i = false; (p *= mul[i]) < n; i = !i);
        // 마지막으로 곱한 수가 9라면 백준이, 2라면 동혁이 이긴다
        printf("%s wins.\n", i ? "Donghyuk" : "Baekjoon");
    }

    return 0;
}