[백준 9655] 돌 게임

돌 게임(9655)

문제 출처 : https://www.acmicpc.net/problem/9655

돌 게임은 다양한 방식으로 출제되고 있는 유명한 문제 입니다. 다양한 돌 게임중 가장 쉬운 형태의 문제 입니다.

우리는 돌을 1개 혹은 3개를 가져갈 수 있습니다. 2개를 가져갈 수 있는 것이 아니라는 점을 기억해야 합니다. 이 때 두 사람은 최선을 다해 게임이 임합니다. 즉 자신이 지는 방향으로는 가지 않는다는 뜻입니다.

문제 이해하기

N개의 돌이 남았을 때 현재 상근이가 게임을 진행하면 누가 이길지를 출력하는 것이 우리가 만들 함수 입니다. 상근이의 차례에 돌이 1개 혹은 3개 남아있다면 무조건 상근이가 이깁니다. 반대로 2개 혹은 4개가 남아 있다면 무조건 창영이가 이기게 됩니다. 그럼 아래와 같은 함수를 만들 수 있습니다.

solve(n, w)

이 함수를 n개의 돌이 있을 때 w의 차례인 경우 승자를 리턴하는 함수라고 정의 하였습니다. w의 값을 문자로 전달해도 되지만 좀 더 쉽게 상근이일 때 0, 창영이일 때 1이라 하겠습니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다

입력 받기

N = int(input())

돌의 개수 N을 입력 받습니다.

함수 만들기

def solve(n, w):
    case1 = solve(n - 1, 1 - w)
    case2 = solve(n - 3, 1 - w)

    if case1 == w:
	return case1
    if case2 == w:
        return case2

    return case1

solve(N, 0)

N개의 돌을 가지고 상근이가 시작할 때 승자는 solve(N, 0)으로 표현할 수 있습니다.

돌을 가져오는 방법은 1개를 가져오는 경우, 3개를 가져오는 경우로 두 가지 입니다. 상근이가 돌을 1개 가져오면 돌의 개수가 1이 줄기 때문에 n값은 n - 1이 됩니다. 그리고 돌을 3개 가져오면 n값은 n - 3이 됩니다.

차례 값은 다음과 같이 변하게 됩니다. 상근이가 시작할 때 w값은 0입니다. 다음 차례가 창영이가 되기 때문에 w 값은 1이 됩니다. 현재 차례가 0이면 다음 차례는 1이 되고, 현재 차례가 1이면 다음 차례가 0이 되는 것을 식으로 표현하면 1 - w가 됩니다. w값이 0이면 1이, 1이면 0이 되는 것을 알 수 있습니다.

이제 식으로 표현하면 다음과 같이 됩니다.

돌을 1개 가져오는 경우가 case1, 돌을 3개 가져오는 경우가 case2입니다. case1과 case2의 승자 중 자신이 이기는 경우를 가져와야 합니다. 따라서 case1의 승자가 w와 같은 경우 case1을 리턴하고, case2의 승자가 w와 같은 경우 case2를 리턴합니다. 둘 다 w가 이긴다면 어느것을 리턴해도 상관 없으니 case1을 리턴합니다. 반대로 둘 다 지는 경우도 어느 것을 리턴해도 상관 없으니 case1을 리턴하는 것입니다.

종료 조건 추가하기

돌 게임을 종료하기 위한 종료조건을 추가해 보겠습니다.

def solve(n, w):
    if n == 1 or n == 3:
        return w
    elif n == 2 or n == 4:
        return 1 - w
    
    case1 = solve(n - 1, 1 - w)
    case2 = -1
    if 3 <= n:
        case2 = solve(n - 3, 1 - w)

    ans = case1
    if case2 == w:
        ans = case2

    return ans

solve(N, 0)

돌이 1개 혹은 3개가 남은 경우 현재 차례가 승자가 됩니다. 그래서 w를 리턴합니다. 반대로 2개 혹은 4개가 남은 경우 상대방이 이기게 됩니다. 따라서 1 - w를 리턴합니다.

다음으로 돌이 3개 이상 남아 있어야 case2를 만들 수 있습니다. 따라서 조건문을 넣어 n이 3보다 큰 경우만 case2를 실행합니다. case2는 실행이 가능할 수도 있고, 불가능할 수도 있습니다. 따라서 초기값으로 -1을 넣어주었습니다. 초기값을 0으로 한다면 상근이가 이긴다는 뜻이기 때문에 0과 1이 아닌 다른 숫자를 사용하였습니다.

승자의 공식을 좀 더 뜯어보면 승자가 있건 없건 기본적으로 case1을 리턴합니다. 그리고 case2가 승자인 경우에만 case2를 리턴하게 됩니다. 그렇기에 승자에 대한 로직을 좀 더 간단하게 바꿔 주었습니다.

메모이제이션

마지막으로 메모이제이션 처리를 해주겠습니다.

dp = [[-1] * 2 for _ in range(N + 1)]
def solve(n, w):
    if n == 1 or n == 3:
        return w
    elif n == 2 or n == 4:
        return 1 - w
    
    if -1 < dp[n][w]:
        return dp[n][w]
    
    case1 = solve(n - 1, 1 - w)
    case2 = -1
    if 3 <= n:
        case2 = solve(n - 3, 1 - w)

    ans = case1
    if case2 == w:
        ans = case2
    
    dp[n][w] = ans
    return ans

dp의 초기값은 -1 입니다. 상근이와 창영이가 각각 0과 1이기 때문에 초기값이 결과와 겹치지 않도록 -1로 한 것입니다. 그리고 해당 값이 -1보다 크다면 결과가 이미 계산되었다는 뜻이기 때문에 해당값을 리턴합니다. 만약 아직 계산이 되지 않았다면 값을 구한 후 해당 값을 메모이제이션 처리를 해줍니다.

출력하기

winner = ["SK", "CY"]
print(winner[solve(N, 0)])

0인 경우 SK를 출력하고, 1인 경우 CY를 출력하도록 변경하였습니다. 이 부분은 자신이 이해하기 쉬운 방식으로 변경하면 됩니다. 아래와 같은 방식으로 출력 하는 것도 하나의 방법 입니다.

print("SK" if solve(N, 0) == 0 else "CY")

전체 코드

전체 코드를 확인해 보겠습니다.

N = int(input())

winner = ["SK", "CY"]

dp = [[-1] * 2 for _ in range(N + 1)]
def solve(n, w):
    if n == 1 or n == 3:
        return w
    elif n == 2 or n == 4:
        return 1 - w
    
    if -1 < dp[n][w]:
        return dp[n][w]
    
    case1 = solve(n - 1, 1 - w)
    case2 = -1
    if 3 <= n:
        case2 = solve(n - 3, 1 - w)

    ans = case1
    if case2 == w:
        ans = case2
    
    dp[n][w] = ans
    return ans

print(winner[solve(N, 0)])

다른 방법 풀이

문제에서 n의 값이 1이나 3이면 w가 무조건 이긴다고 하였습니다. 잘 생각해보면 돌의 개수가 홀수로 남은 경우 다음 내 차례가 되었을 때 항상 홀수가 되고, 짝수라면 항상 짝수가 됩니다. 그럼 복잡한 계산이 필요없이 아래와 같이 나타낼 수 있습니다.

N = int(input())
print("SK" if N % 2 == 1 else "CY")

다빈치코딩