돌 게임
이번 주에는 돌 게임 1~7번까지 7문제를 리뷰해보고자 한다.
돌 게임(9655번)
문제
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다
코드
N=int(input())
if N%2==1:
print("SK")
else:
print("CY")풀이
돌을 1개 혹은 3개 가져가기 때문에 모든 경우가 홀수여서 몇개를 가져가든 승자는 변하지 않는다. 그래서 단순하게 N이 홀수면 상근이가 승리하고, 짝수이면 창영이가 승리한다.
돌 게임2(9656번)
문제
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 지게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
코드
N=int(input())
if N%2==0:
print("SK")
else:
print("CY")풀이
위의 문제와 완전히 동일하고 승패만 바뀌었다. 돌을 1개 혹은 3개 가져가기 때문에 모든 경우가 홀수여서 몇개를 가져가든 승자는 변하지 않는다. 그래서 단순하게 N이 홀수면 창영이가 승리하고, 짝수이면 상근이가 승리한다.
돌 게임3(9657번)
문제
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
코드
winner=["NONE"]*1010
winner[1]="SK"
winner[2]="CY"
winner[3]="SK"
winner[4]="SK"
N=int(input())
for x in range(1,N):
for i in [1,3,4]:
if winner[x+i]!="SK":
if winner[x]=="SK":
winner[x+i]="CY"
else:
winner[x+i]="SK"
print(winner[N])풀이
이번에는 4개를 가져가는 경우가 생겨서 케이스가 바뀌었다. 나는 다이내믹 프로그래밍이라는 DP를 활용하여 코드를 작성하였는데 만약 돌의 개수가 N개일 때, N-1,N-3,N-4의 결과가 모두 상근이가 이기는 경우, 창영이가 승리하고 그 외의 경우 상근이가 승리한다.
돌 게임4(9658번)
문제
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 지게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
코드
winner=["NONE"]*1010
winner[1]="CY"
winner[2]="SK"
winner[3]="CY"
winner[4]="SK"
N=int(input())
for x in range(1,N):
for i in [1,3,4]:
if winner[x+i]!="SK":
if winner[x]=="SK":
winner[x+i]="CY"
else:
winner[x+i]="SK"
print(winner[N])풀이
위의 문제와 완전히 동일하고 승패만 바뀌었다. 초기 값만 바꾸어주면 정답을 얻을 수 있다.
돌 게임5(9659번)
문제
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
코드
N=int(input())
if N%2==1:
print("SK")
else:
print("CY")풀이
돌게임 1번 문제와의 차이점은 N의 입력값이 1조(1,000,000,000,000)까지 늘어났다는 점인데 가져가는 경우의 수가 똑같이 1개 or 3개이기 때문에 같은 코드를 이용했다.
돌 게임6(9660번)
문제
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
코드 1
winner=["NONE"]*1000000000005
winner[1]="SK"
winner[2]="CY"
winner[3]="SK"
winner[4]="SK"
N=int(input())
for x in range(1,N):
for i in [1,3,4]:
if winner[x+i]!="SK":
if winner[x]=="SK":
winner[x+i]="CY"
else:
winner[x+i]="SK"
print(winner[N])풀이 1
돌게임 3번과의 차이점은 N의 입력값이 1조(1,000,000,000,000)까지 늘어났다는 점이다. 돌게임 3에서 이용했던 코드를 그대로 입력하면 메모리 초과가 나온다. DP를 사용하려면 1조 개짜리 리스트를 만들어야 하는데 1byte의 bool만을 표현하는 리스트를 이용해도 무려 1TB(테라바이트)라는 용량이 나오게 된다.
코드 2
N=int(input())
if N%7==0 or N%7==2:
print("CY")
else:
print("SK")풀이 2
DP를 쓰지 않고 정답을 구하는 방법을 생각하며 1부터 결과 값을 쓰다 보면 7개마다 정답이 반복된다는 것을 확인할 수 있다. 그래서 7으로 나눈 나머지가 0 or 2이면 창영이가 승리하고 그 외에는 상근이가 승리한다.
돌 게임7(9661번)
문제
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 4x개 만큼 가져갈 수 있다. 즉, 가능한 개수는 1, 4, 16, 64, ...개 이다. 4x개만큼 돌을 가져갈 수 있는 방법이 없는 사람이 게임을 지게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
코드
N=int(input())
if N%5==0 or N%5==2:
print("CY")
else:
print("SK")풀이
이번에도 문제가 바뀌었는데 N의 최대값이 여전히 1조 이기 때문에 DP 같은 방법을 사용할 수 없다. 그래서 1부터 계속 써내려가다 보면 5개마다 반복되는 규칙을 찾을 수 있는데 이게 숫자가 커졌을 때까지 계속 적용되는 규칙인지 확인하고 싶었다.
그래서 DP를 활용해서 구한 결과와 나머지를 이용해서 구한 결과가 동일한지 확인하는 코드를 작성하여 10,000까지 돌려보았다.
winner=["NONE"]*20010
winner[1]="SK"
winner[2]="CY"
winner[3]="SK"
winner[4]="SK"
winner[5]="CY"
mod=["NONE"]*20010
for N in range(1,15000):
if N%5==0 or N%5==2:
mod[N]="CY"
else:
mod[N]="SK"
for x in range(1,N):
for i in [1,4,16,64,256,1024,4096]:
if winner[x+i]!="SK":
if winner[x]=="SK":
winner[x+i]="CY"
else:
winner[x+i]="SK"
for N in range(1,10000):
print(N,winner[N]==mod[N])
이 프로그램을 돌리자 컴퓨터가 굉음을 내며 아파하면서 오랜 시간이 걸렸지만 다음과 같은 결과를 얻을 수 있었다.
이를 통해 1~10,000까지의 범위 내에서는 규칙이 알맞게 적용된다는 것을 확인하고 제출하여 정답을 얻었다.
만은 진짜 광기다…