[구현/게임이론] 백준 9659 돌 게임 5 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

9659번: 돌 게임 5

 

 

2. 문제 풀이

2023.07.03 - [Algorithm] - [동적계획법/DP] 백준 9656 돌 게임 2 - 파이썬(Python)

[동적계획법/DP] 백준 9656 돌 게임 2 - 파이썬(Python)

 돌 게임 2 풀이 때 발견한 규칙을 적용하는 문제입니다.

 DP 테이블을 보면 n의 홀짝에 따라 결과가 바뀌곤 했죠.

 

 

3. 코드

# 입력
n = int(input())

# DP
if n == 1:
    print('SK')
elif n == 2:
    print('CY')
elif n == 3:
    print('SK')
else:
    dp = [-1] * (n+1)
    dp[1] = 'SK'    # 창영이 이김
    dp[2] = 'CY'    # 상근이 이김
    dp[3] = 'SK'    # 창영이 이김

    for i in range(4, n+1):
        # 돌이 1개 혹은 3개 남은 상황일 때
        if dp[i-1] == 'CY' or dp[i-3] == 'CY':
            dp[i] = 'SK'
        else:
            dp[i] = 'CY'
    print(dp[n])

 이전과 같은 방식으로 하면 '메모리 초과'가 뜹니다.

 n의 입력범위가 무진장 크므로.... DP로는 못 풉니다.

 

 

# 입력
n = int(input())

# 홀수면 SK, 짝수면 CY
print('SK' if n%2 == 1 else 'CY')

 위와 같이 규칙을 찾아서 출력해야 합니다.