[SWEA] 3459 승자 예측하기

문제

SWEA 3459 : 승자 예측하기

SW Expert Academy

접근

이 문제는 N의 값에 따라 Alice와 Bob의 승리가 정해져 있다.(둘 다 최적의 수를 둔다고 가정했을 때)

그리고 이 승리에는 규칙이 있는데

N의 값이 1일 때는 Bob의 승리 (1개)

2, 3, 4, 5 는 Alice의 승리 (4개)

6, 7, 8, 9 는 Bob의 승리 (4개)

10, 11, 12, ... , 24, 25 는 Alice의 승리 (16개)

26, 27, 28, ... , 40, 41 은 Bob의 승리 (16개)

.

.

.

이런 식으로 승리가 정해져 있다. 즉 4배씩 증가하고 있음을 알 수 있다. 따라서 4배씩 증가시켜주면서 N에 도달했을 때 누가 승리하는지 따져보면 정답을 알 수 있다.

이때 주의할 점은 cin, cout으로 입출력 시 시간 초과가 난다. scanf, printf로 입출력해주도록 한다.

또 N의 값은 10^18 이므로 int가 아닌 long long으로 받아준다.

 

코드

#include <stdio.h>

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        long long num, add = 1, fl = 0, temp = 1;
        scanf("%ld", &num);
        while (add < num) {
            if (fl == 0) {
                temp *= 4;
                fl = 1;
            } else
                fl = 0;
            add += temp;
        }
        if (fl == 1)
            printf("#%d Alice\n", i + 1);
        else
            printf("#%d Bob\n", i + 1);
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study