백준 4342번: 유클리드 게임 (Python)

문제링크

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

문제 총평

- 수학을 못하면 고생한다  

 

수정 후 풀이

- 실제로는 이 문제는 게임이론에 관한 문제입니다.

- 또한 이 문제는 특정 인물이 주도권을 잡는 순간 무조건 그 게임을 이길 수 있는 형태의 게임입니다.

- 그러므로 처음으로 게임의 주도권을 잡는 순간인 큰수에서 뺄수있는 작은수가 2개 이상(a//b > 1)일 때 자기 턴을 가지고 있는 쪽이 반드시 승리하게 됩니다.

 

 

while 1:
    a,b = map(int, input().split())
    if a == 0 and b == 0:
        break
    a,b = max(a,b), min(a,b)
    ans = 'A'
    while a%b:
        if a//b > 1:
            print(ans,'wins')
            break
        a,b = b, a%b
        ans = 'A' if ans == 'B' else 'B'
    else:
        print(ans,'wins')

 

 

 

 

 

수정 전 풀이

 

문제 접근방식

 

- 결론부터 말하자면 이 문제는 제목처럼 유클리드 호제법을 사용하는 문제입니다.

- 하지만 저는 유클리드 호제법을 사용하는 풀이를 떠올리지 못해 나름대로 푼 방법을 공유하고자 합니다.

 

- 먼저 이 게임은 반드시 이기는 공식이 존재합니다.

- 각각의 플레이어는 큰 수에 빼는 작은 수의 배수를 마음대로 정할 수 있기 때문에 가능한 수를 미리 구해 arr에 저장합니다. 이는 예를들어 34, 12 일때 34 에서 최대 12 * 2 만큼을 뺄 수 있으므로 각각의 플레이어는 2개의 경우 안에서 뺄 지 안뺄지를 정할 수 있습니다.

- 이때 승자가 정해지는 맨 마지막 수를 확인합니다.

- 맨 마지막 수가 1 이라면 A인 동혁이가 이기기 위해서는 그 전 게임이 반드시 B인 동규가 게임을 끝냈어야 합니다.

- 이때 그 전 게임에서도 경우가 갈리는데 만약 경우의 수가 1이라면 그 전전 게임은 반드시 A가 끝냇어야 하고 경우의 수가 2 이상이라면 그 전의 게임을 B가 끝냈어야 합니다 -> 왜냐하면 경우의 수가 2 이상인 경우 먼저 선공을 가지고 있는 쪽이 이번 턴을 끝낼 수 있는 통제권을 가지기 때문입니다.

- 이런식으로 현재 시작해야하는 사람과 그 전에 끝내야 할 사람을 arr를 거꾸로 탐색하면서 알 수 있고 처음 시작까지 왔을 때 그 경우를 보면 누가 이길 수 있는지 알 수 있습니다.

- 정답 출력 코드에서 now = 'A' 라는것은 arr[1]에서 시작이 A여야 한다는 것이고 그 뜻은 처음 시작이 B로 끝나야 한다는 것을 알 수 있습니다.

- 하지만 arr[0] == 1이라면 반드시 A로 끝나게 되어 A는 지게되고 1이 아니라면 A는 반드시 B로 끝나게 할 수 있으므로 무조건 이길 수 있습니다.

- now = 'B'인 경우는 무조건 첫 시작을 B로 끝나게 할 수 있으므로 A가 이기는 거구요.

 

 

정답코드 

while 1:
    a,b = map(int, input().split())
    if a == 0 and b == 0:
        break
    a,b = max(a,b), min(a,b)
    if a%b == 0:
        print('A wins')
        continue
    arr = []
    while a%b:
        arr.append(a//b)
        a,b = b, a%b
    if len(arr) == 1 and arr[0] == 1:
        print('B wins')
        continue
    now, pre = 0,0
    if arr[-1] == 1:
        now = 'B'
        pre = 'A'
    else:
        now = 'A'
        pre = 'B'
    for i in range(len(arr)-2,0,-1):
        if arr[i] == 1:
            if pre == 'A':
                now = 'A'
                pre = 'B'
            else:
                now = 'B'
                pre = 'A'
        else:
            now = 'A'
            pre = 'B'
    if now == 'A':
        if arr[0] == 1:
            print('B wins')
        else:
            print('A wins')
    else:
        print('A wins')

 

문제 풀이 후 생각

- 수학 공부를 열심히 합시다...

 

 

모르는게 있다면 댓글 또는 godzz733@naver.com으로 메일 남겨 주세요