[BOJ] #9655. 돌게임1 (Python)

mingguriguri·2022년 10월 30일

DP 단순연산 백준 알고리즘

Python으로 공부하는 Algorithm

목록 보기

3/10

#9655. 돌게임1

링크: https://www.acmicpc.net/problem/9655
유형: 다이나믹 프로그래밍, 단순연산
작성일시: 2022년 10월 22일 오후 2:57

🎯게임이론

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

사례 - 죄수의 딜레마

Untitled

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

📑문제설명

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

탁자 위 돌 개수 N개

상근이와 창영이는 턴을 번갈아가면서 돌을 가져간다 (1개 또는 3개

마지막 돌을 가져가면 이긴다.

상근이 먼저 시작함

두 사람은 완벽하게 게임한다. (위에서 말한 게임이론에서와 같이 자신에게 이득이 되도록한다.

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

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

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

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**

🚨문제점들

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

📌배운 점

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