[백준 9655] 돌게임_python

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

9655번: 돌 게임

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

문제 해결

1.bfs

2.DP

 

DP로 문제를 해결했다. D(i)에 대한 정의를 숫자 i일 때 승자를 D배열에 저장하는 생각으로 점화식을 짜 나가다

D(1) : 상근

D(2) : 창영

D(3) : 상근

D(4) : 창영

D(5) : 상근

...

D(1)일 때 최선은 상근, 2일 때는 상근 1, 창영 1 -> 창영, 3일 땐 상근(1,1,1 or 3)..

위와 같은 규칙을 발견하였고. D(i)일 때의 최선인 사람이 D에 정의가 되어있고 1 혹은 3으로 만큼만 움직일 수 있기에 D(i)와 D(i+1)은 서로 승자는 다른 사람이 될 수밖에 없다.(최선의 선택인 1개가져가기)

그것을 규칙으로 식으로 옮기면 짝수일 땐 창영, 홀수일 땐 상근이가 답이 된다.

if int(input())%2 ==0:
    print('CY')
else:
    print('SK')

아래 코드는 재미로만 봐주길 바랍니다. 비트 연산을 이용하여 뒤 배열의 인덱스 번호에 따라 앞 배열의 값을 출력하는 형식이다.

print(['CY','SK'][int(input())%2])