링크: https://www.acmicpc.net/problem/9655
유형: 다이나믹 프로그래밍, 단순연산
작성일시: 2022년 10월 22일 오후 2:57
폰 노이만
에 의해 게임 이론의 기초가 달성됨.돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
- 탁자 위 돌 개수 N개
- 상근이와 창영이는 턴을 번갈아가면서 돌을 가져간다 (1개 또는 3개
- 마지막 돌을 가져가면 이긴다.
- 상근이 먼저 시작함
- 두 사람은 완벽하게 게임한다. (위에서 말한 게임이론에서와 같이 자신에게 이득이 되도록한다.
INPUT
첫째 줄에 N ( 1≤N≤1000)
OUTPUT
상근이가 이기면 SK
, 창영이가 이기면 CY
출력
1이나 3이라는 숫자 자체가 애매해보인다. 이럴 때는 1~5까지 나열해보도록한다.
N = int(input())
if N % 2 == 0 :
print("CY")
else:
print("SK")
지난 시간에 우린 다이나믹 프로그래밍에 대해 배웠다. 이 문제는 다이나믹 프로그래밍과 관련된 문제는 아니지만, 복습할 겸 활용해보았다.
크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구한다.→ 이는 분할 정복과 같다.
이 과정에서 Memorization이 사용된다는 점이 분할 정복과 다르다.
→ 이미 계산한 결과는 배열에 저장!
다이나믹 프로그래밍 방식으로 돌게임 문제를 풀어보자.
이전의 게임 턴 값을 이용해서 푸는 방식 이다.
📍 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]까지는 값을 미리 지정해준다.
# 돌 개수 입력받기
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
**
🚨문제점들
/
)는 꼭 int
형으로 바꾸어주어야 한다.