[백준] #9655 돌 게임 (Python)

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

🎯게임이론

• 폰 노이만에 의해 게임 이론의 기초가 달성됨.
• 게임 진행 주체들 간에 상호 의존성이 존재하여 상대방의 의사결정이 자신의 손익에 영향을 미친다는 사실을 고려해야 하는 게임 상황 가운데 합리적인 주체가 어떤 의사결정을 하는가를 연구하는 학문이다.
• 주체는 합리적이므로 게임의 참가자들은 자신의 이익을 극대화하는 방향의 의사결정을 하게 되며, 비이성적인 선택을 하지 않는다는 전제 조건이 붙는다.
• 참가자의 합리성은 모든 참여자 사이의 공통지식이라는 조건이 붙는다.

사례 - 죄수의 딜레마

• 개인에게는 최선이나 결론적으로는 최선이 아닌 것이 딜레마이다.
• 내쉬 균형: 상대 전략을 전제로 자신의 이익을 최대화하는 전략을 선택해 형성된 균형
• ‘경제학의 아버지’라 불리는 애덤 스미스는 “경제적 인간은 언제나 자신에게 최고로 이익이 되는 선택을 한다”고 말함
• → 내쉬의 반박: 최고로 이득이 되는 선택을 위해서는 상대방도 고려해야한다.

---

📑문제설명

돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

1. 탁자 위 돌 개수 N개
2. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져간다 (1개 또는 3개
3. 마지막 돌을 가져가면 이긴다.
4. 상근이 먼저 시작함
5. 두 사람은 완벽하게 게임한다. (위에서 말한 게임이론에서와 같이 자신에게 이득이 되도록한다.

INPUT 첫째 줄에 N ( 1≤N≤1000)

OUTPUT 상근이가 이기면 SK, 창영이가 이기면 CY출력

---

🧐풀이

✔풀이 1 - 직관적 풀이

1이나 3이라는 숫자 자체가 애매해보인다. 이럴 때는 1~5까지 나열해보도록한다.

• n=1 → 상근이가 먼저 1개 가져가고 게임 끝 ⇒ SK
• n=2 → 상근 1, 창영 1 ⇒ CY
• n=3 → 상근3 or 상근1 창영1 상근1 ⇒ SK
• n=4 → 상근3 창영1 or 상근1 창영1 상근1 창영1 ⇒ CY
• n=5 → 상근3 창영1 상근1 ⇒ SK이러한 경우들을 보면 n이 홀수일 때 상근이가 이기고, n이 짝수일 때 창영이가 이긴다는 것을 알 수 있다.
• 코드는 다음과 같다.
• …

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

---

동적 프로그래밍을 적용해보자!!

지난 시간에 우린 다이나믹 프로그래밍에 대해 배웠다. 이 문제는 다이나믹 프로그래밍과 관련된 문제는 아니지만, 복습할 겸 활용해보았다.

동적프로그래밍(Dyanmic Programming)

• 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구한다.→ 이는 분할 정복과 같다.
• 이 과정에서 Memorization이 사용된다는 점이 분할 정복과 다르다. → 이미 계산한 결과는 배열에 저장!
• 다이나믹 프로그래밍 방식으로 돌게임 문제를 풀어보자.

✔풀이 2 - 다이나믹 프로그래밍을 이용한 답

분석

• 우리가 풀어야할 피상적인 큰 문제는 누가 이겼는지 구하는 것 이다.
• 승자가 누군지 구하려면 누가 마지막에 돌을 가져갔는지를 알아야한다.
• 두 사람이 완벽하게 게임을 진행한다.
• 무조건 턴 개수는 최소가 되도록한다.
• dp[1] = 1 → 상근 승 dp[2] = 2 → 창영 승 dp[3] = 1 → 상근 승 dp[4] = 2
  dp[5] = 3 dp[6] = 2 dp[7] = 3 dp[8] = 4 dp[9] = 3 dp[10] = 4

이전의 게임 턴 값을 이용해서 푸는 방식 이다.

<aside> 📍 n은 돌의 개수, dp[n]은 돌의 개수가 n일때 최소 턴 개수, dp = 최소 턴의 개수 dp[n] = dp[n-1] + 1 or = dp[n-3] +1

</aside>

N = int(input())  # input
 
# dp = [0 for i in range(N)]
# dp = [0] * N
dp = [0] * (1000 + 1)

dp[1] = 1
dp[2] = 2
dp[3] = 1
 
for n in range(4, N+1):
    dp[n] = min(dp[n-1], dp[n-3]) + 1
 
if dp[N] % 2 == 1:
    print('SK')
else:
    print('CY')

돌의 개수(N) 1 2 3 4 5 6 7 8 9 10

턴의 개수(dp)

1

2

1

2

3

2

3

4

3

4

min(dp[n-1] + 1 , (dp[n-3] +1))을 이용한다. 마지막에 이기는 사람이 이기기 때문에 규칙에 따라 이전 턴 개수 + 1 해준다.

근데 이전 턴에서 3개를 가져갔는지, 1개를 가져갔는지 모른다. 따라서 (돌의개수 - 1)과 (돌의개수 - 3) 일 때로 경우를 나눠서 생각한다.

이 둘 중에 최소가 되는 값에 1을 더한 값이 + 1이 최소 턴의 개수가 된다.

이때 dp[n-3]을 연산하기 위해서 dp[1]~dp[3]까지는 값을 미리 지정해준다.

✔풀이 3 - 내 풀이

# 돌 개수 입력받기
N = int(input())
 
#리스트 초기화
dp = [0 for i in range(N+1)]

for i in range (1, N+1):
    dp[i] = int(i/3) + int(i%3) 
    print(i, dp[i])

if dp[N] % 2 == 1:
    print('SK')
else:
    print('CY')

돌의 개수(N) 1 2 3 4 5 6 7 8 9 10

턴의 개수(dp)

1

2

1

2

3

2

3

4

3

4

다음 규칙을 보고 식을 만들었다. i는 최대 3의 차이가 있으므로 나누기 연산자와 나머지 연산자를 이용하였다.

**dp[i] = i/3 + i%3**

🚨문제점들

1. 처음엔 IndexError가 났다. IndexError가 나는 이유는 보통 Index의 값의 범위를 벗어나서이다. 인덱스의 범위는 N이 아니라 N+1로 설정해주어야 한다.
2. 나누기 연산자(/)는 꼭 int형으로 바꾸어주어야 한다.

📌배운 점

• 동적계획법에 대해서 애매모호하게 알고 있었는데, 이번 문제를 통해서 더 확실하게 알게 되었다. 이론만 알고 있고 코드 구현은 다소 어려웠는데 이번에는 제대로 감을 찾게 되었다!
• 동적계획법 사용 시, 배열에 어떤 값이 들어가야할지 고민해보자! 고민하다보면 길이 보인다! (근데 보통 턴의 개수 / 경우의 수 등 가능성이 나오는 것 같다. 아직 이런 문제만 풀어서 그런 걸수도!))