99클럽 코테 스터디 26일차 TIL: 베스킨라빈스 게임

오늘의 문제 | 9655. 돌 게임

이번 문제는 DP 문제라고 한다. 이미 풀었던 문제라 어떤 풀이로 풀어야 할 지를 떠올려보고, 예전 풀이와 간단하게 비교해보려 한다.

아이디어: 베스킨라빈스 31

베스킨라빈스 게임에서 상대방이 어떤 수를 말하든 무조건적으로 둘의 합이 4가 되게 하는 방법처럼, 유리한 고점을 차지한 이후로는 상대방이 말하는 숫자와 다른 숫자를 말하여 원하는 대로 합을 이끌어나갈 수 있다.

시작은 상근이가 먼저하고, N을 4로 나눈 나머지를 체크하여 남는 숫자에 따라서 이기는 사람이 달라진다는 것을 알수 있다. 즉, 1 2 3의 케이스만 확인하면 된다.

 

(1) 4의 배수인 경우: 상근이가 뭘 말하든 창영이는 합이 4가 되게 하면 되므로 CY

(2) 나머지가 1인 경우: 상근이는 1을 말하면 무조건 이긴다. 따라서 SK

(2) 나머지가 2인 경우: 상근이가 1을 말하면 창영이가 1을 말하므로 무조건 진다. 상근이가 3을 말해도 창영이가 3을 말하므로 무조건 진다. 따라서 CY

(3) 나머지가 3인 경우: 상근이가 3을 말하면 무조건 이긴다. 따라서 SK

 

이를 통해서 홀수면 SK, 짝수면 CY를 출력하면 된다는 것을 알아냈다.

print("CSYK"[int(input())%2::2])

가장 숏코드를 짜봤다. 사실 이번 문제는 DP라고 하기 보다는 게임 이론으로 풀었다고 생각한다.

n = int(input())

if n%4 == 0 or n%4 == 2:
    print("CY")
elif n%4 == 1 or n%4 == 3:
    print("SK")

예전 코드를 봤을 때도 같은 풀이로 풀었다는 것을 확인할 수 있다. 다만 2022년에 풀었던거라 내 머리로 직접 떠올렸을지는 모르겠다.

오늘의 회고

어쩌다보니 예전과 같은 논리지만 조금더 짧게 구성해봤다. 확실히 생각의 흐름이 알고리즘을 처음 시작했을 때보다 좋아졌다는 걸 느꼈다. 확실히 나만의 로직을 떠올려서 해결할 수 있었다는 게 만족스럽다.