[SWEA] D4 : 승자 예측하기(3459) Python

SWEA D4 문제를 아직 많이 풀어보진 못했지만, 혁진이의 프로그래밍 다음으로 어려웠던 문제였다. 결론부터 말하자면 이문제의 핵심은 최선을 다한다는 것이고, 이를 구현하기 위해서 뒤에서부터 접근하면 한결 편해지는 문제였다.

문제를 간략히 소개하자면 Alice와 Bob이 목표숫자 N을 정해놓고 숫자 게임을 한다. 숫자게임은 자신의 차례일 때 숫자 x를 x*2로 키우거나 x*2+1로 키울 수 있고, 자신의 차례일 때, 어떻게 숫자를 키우더라도 N보다 크게 된다면 그 사람의 패배이다. 우리가 흔히 아는 31게임이랑 비슷하지만 숫자를 키우는 방식에서 조금 차이가 있다. 문제는 Alice와 Bob이 최선을 다해 게임을 할 때, 누가 이기게 되는지  묻는다.

한번씩 31게임을 할 때, 계산 따위 하지 않고 운에 모든 것을 맡기는 나한테는 누가 이기게 될지 결정하는 것이 너무 어려웠다. 더구나 이 문제에서 가장 어려웠던 점은 'Alice와 Bob이 최선을 다해 게임을 한다면' 이 문구였다. (최선이 현재의 상황에서 최선인지, 게임 결과 전체를 안 상태에서 최선인지 판단이 어려웠다.) 아직 나는 최선을 다해 알고리즘 문제를 풀 수 있지만, 알고리즘이 최선을 다해 작동하게는 할 수 없었다.

그래도 문제를 풀긴위해 어떻게 풀지 고민하며 가장 먼저 떠올랐던 것은 BFS를 이용하는 것이었다. 'BFS를 이용하여 노드를 내려가다가 한 명이 N//2 보다 큰 수를 부르는 경우 그 사람이 이기게 하지 않을까?'를 생각하고  N의 범위를 봤는데 1 <=N <=10^18을 보고 바로 생각을 접었다.(최선을  고려하지 않은 방법이기도 했다.)

BFS는 시간과 메모리제약상 절대 안 될 것 같았고, 내 지식에서는 그리디로 접근하는 방법밖에 남지 않았다. 우선, 현실에서도 31게임을 최선을 다하는 것은, 나처럼 운에 맡기는 것이 아닌 경우의 수를 생각해서 첫 시작부터 내가 이기게 만드는 것이기 때문에 이 문제에서 최선도 둘 다 이기는 법을 알고 있다고 가정하고 접근하기로 했다.

a와 b가 게임을한다면 N이 12일 때 a가 만들 수 있는 숫자가 6과, 7이고, a가 최선을 다한다면 무슨 수를 선택해야 할까? 바로 7을 선택해야 한다. 즉 b입장에서는 a가 7을 부르면 안 되기 때문에 2(N//2-1)를 불러야 한다. 즉, 이게임은 먼저 시작하는 b가 2를 부르면 무조건 이기는 게임이 된다.

이 점을 생각하여 다시 문제로 돌아온다면, 문제에서는 Alice가 항상 2와 3을 고르는 것으로 시작한다. 하지만 나는 이 점을 집중하기 보다 누가 게임을 끝낼 수 있는 숫자를 부를 수 있는 사람(코드 내부에서 공격자로 표현)인지 집중했다. 그리고 항상 먼저 시작할 수 있는 Alice를 공격자 Bob을 방어 자라 생각하고 문제를 풀었다.

N>3일 때는 공격자와 방어자가 자신이 원하는 수를 부르기위해, 상대방이 원하는 수를 못 부르게 하기 위해 N//2+1과 N//2-1일 부르며 내려간다. 하지만 N <3일 때는 자연스럽게 공격자가 원하는 숫자를 고를 수 있는 차례가 된다. N이 2와 3이거나 0인 경우(원래 3이나 2이어야 하지만 while문이 한번 더 작동한 경우) 공격자 Alice는 2나 3으로 시작하여 무조건 이길 수 있을 것이다.
하지만, N==1인 경우  Alice가 원하는 공격숫자를 고르지 못할 것이고 방어자인 Bob이 이기게 될 것이다

이를 코드로 나타낸다면,

T = int(input()) + 1

for tc in range(1,T):
    N = int(input())
    print(f'#{tc}', end=' ')
    while N > 3:
        N = N // 2 + 1 # 공격자가 부르고 싶은 수
        N = N // 2 - 1 # 공격자가 부르고 싶은 수를 못부르게 막는 방어자의 수

    if N >= 2 or N==0: # 공격자가 2,3의 수를 시작으로 자신이 원하는 수를 만들 수 있다면 Alice 승
        print('Alice')

    else:
        print('Bob')

이렇게된다. 풀이 방법만 생각해 낸다면, 코드는 엄청 간단한 문제였던 것 같다.

하루 한개 알고리즘... 오늘도 파이팅!

 

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWFPoj1qANoDFAV0&categoryId=AWFPoj1qANoDFAV0&categoryType=CODE&problemTitle=%EC%8A%B9%EC%9E%90&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1