====== 돌 게임 4 ====== ===== 풀이 ===== * [[ps:problems:boj:9657]]에서 승리조건과 패배조건만 뒤바뀐 문제. * [[ps:problems:boj:9657]]과 마찬가지로 N의 범위가 작으므로 DP를 통해서 O(N)에 풀수 있다. dp테이블에서 N=0일때의 값만 바꿔주고 dp를 돌리면 된다. ===== 코드 ===== """Solution code for "BOJ 9658. 돌 게임 4". - Problem link: https://www.acmicpc.net/problem/9658 - Solution link: http://www.teferi.net/ps/problems/boj/9658 Tags: [Game theory] """ def main(): N = int(input()) is_win_pos = [False] * (N + 5) is_win_pos[0] = True for i in range(N + 1): if not is_win_pos[i]: is_win_pos[i + 1] = is_win_pos[i + 3] = is_win_pos[i + 4] = True print('SK' if is_win_pos[N] else 'CY') if __name__ == '__main__': main() {{tag>BOJ ps:problems:boj:실버_2}}