[알고리즘/동적 계획법] 9655번 : 돌 게임 - python

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

9655번: 돌 게임

 

---

• 문제
• 소요시간: X

---

• 설계하기(접근방법) 동적 계획법으로 풀어보기

1. n을 입력받는다

2. 알고리즘 해석

돌을 가져가는 경우

1 개 or 3 개 (2개만 가져가는 경우는 없다)

1 = 상근, 0 = 창영

 

돌이 1개 일때 

1 -> 상근이가 가져간다 rock[1] = 1 

돌이 2개 일때

1, 1 -> 창영이가 가져간다 rock[2] = 0

돌이 3개 일때

 

3 or 1,1,1 -> 상근이가 가져간다 rock[3] = 1

돌이 4개 일때

1,3 or 3,1 or 1,1,1,1 창영이가 가져간다 rock[4] = 0

돌이 5개 일때

1,3,1 or 3,1,1 or 1,1,3 or 1,1,1,1,1 rock[5] = 1

 

즉 보다보면 

상근이가 3개를 가져가는 경우와

상근이가 1개를 가져가는 경우로 나눠진다

 

이는 즉

rock[n] = 창영이가 먼저 시작하는 rock[n-3]

or rock[n] = 창영이가 먼저 시작하는 rock[n-1]과 같다.

즉 rock[5] = reverse rock[2] or rock[5] = reverse rock[4]이다.

 

[n-1] 이나 [n-3]이 존재한다면 [n]은 그 값의 반대이다.

[n-1]은 [n-3]에서 서로 1개씩 돌을 가져간 경우(2번)밖에 없으므로 [n-1] = [n-3]임을 증명할 수 있다.

 

---

• 코드(출력)

n = int(input())

rock = [0 for _ in range(1001)]

rock[1] = 1  # 상근
rock[2] = 0  # 창영
rock[3] = 1  # 상근

for i in range(4, n+1):
    if rock[i - 1] == 1 or rock[i - 3] == 1:
        rock[i] = 0
    else:  # rock[i - 1] ==  or rock[i - 3] == 1
        rock[i] = 1

if rock[n] == 1:
    print("SK")
else:
    print("CY")

 

---

• 얻어갈 부분

1. 동적 계획법을 어떻게 사용하는지 조금 더 알게되었다.

2. 점화식을 찾아야 할 것 같다