9660. 돌 게임 6

9660 문제 보기

Difficulty : Gold 5

Status : Failed

Time : 00:25

접근 방식

DP로 접근하려고 했지만, N의 최댓값이 1,000,000,000,000이어서 분명 시간초과가 날 것 같았다.
DP 테이블을 출력해 확인한 결과,

#1 - 상근
#2 - 창영
#3 - 상근
#4 - 상근
#5 - 상근
#6 - 상근
#7 - 창영
#8 - 상근
#9 - 창영
#10 - 상근
#11 - 상근
#12 - 상근
#13 - 상근
#14 - 창영
#15 - 상근
#16 - 창영
#17 - 상근
#18 - 상근
#20 - 상근
#21 - 창영

2부터 시작해서 +5, +2, +5, +2, ... 순서로 창영이가 이기는 경우라는 규칙을 발견했다.
따라서 N을 7로 나눈 나머지가 0 또는 2일 때에는 창영이의 승, 나머지 경우에는 상근이의 승으로 구별할 수 있다.

최종 코드

N = int(input())
print('CY' if N % 7 == 0 or N % 7 == 2 else 'SK')

배운점

게임 이론: DP라는 해결방식으로부터 컴퓨터의 계산능력을 이용해 무지성 풀이가 가능한 방법
게임 이론에 대한 내용을 많이 참고한 블로그 URL이다!