99클럽 코테 스터디 26일차 TIL / 수학&DP(다이나믹 프로그래밍)

✏️ 문제

[백준/BOJ] 9655번: 돌 게임(https://www.acmicpc.net/problem/9655)

 

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S5

✅ 소요 시간: 5분

✅ 권장 시간: 1시간 15분

 

💡 풀이

1) 문제 이해

문제를 보자마자 배스킨라빈스 31 게임이 생각났다. 저 게임에 필승 규칙이 있는 것처럼 이 문제도 분명히 상근이가 무조건 이기거나 지는 규칙이 있을 거라고 생각했다.

 

나는 수학적인 방법(이라고 하기에는 너무 간단하긴 하지만)으로 풀어서 맞았는데 문제 분류에 '다이나믹 프로그래밍'이 있길래 DP로도 풀어보았다.

 

2-1) 수학 - 아이디어 흐름 및 수학적 증명

① N이 홀수일 때

문제에서 한 번에 가지고 갈 수 있는 돌은 1개 아니면 3개라고 했기 때문에 전체 돌 개수가 1개이거나 3개이면 무조건 상근이가 이기게 된다.

 

여기서 값을 좀 더 확장시키면서 돌 개수가 홀수인 경우를 따져봤다.

 

N = 5 → 상근 1, 창영 1, 상근 3(승) / 상근 1, 창영 3, 상근 1(승) / 상근 3, 창영 1, 상근 1(승)

N = 7 → 상근 1, 창영 1, 상근 1, 창영 1, 상근 3(승) / 상근 1, 창영 1, 상근 3, 창영 1, 상근 1(승) / ...

 

N이 홀수면 어떻게 해도 상근이가 이기게 되는 것을 알 수 있다.

 

② N이 짝수일 때

N이 2일 때 상근 1, 창영 1로 창영이가 이기게 된다.

 

①에서와 동일하게 N이 2 초과 짝수인 경우에 대해 확인해보자.

 

N = 4 → 상근 1, 창영 1, 상근 1, 창영 1(패) / 상근 1, 창영 3(패) / 상근 3, 창영 1(패)

 

N이 6일 때는 적지 않아도 창영이가 이기는 게 명백하다.

 

③ 수학적 증명

위의 접근 방식은 '이렇게 하니까 되더라' 식에 가까운 것 같아 챗지피티의 도움을 받아 수학적으로 어떻게 증명할 수 있는지 확인해봤다.

---

 

< 귀납법 적용 >

 

가설: N이 홀수면 상근이가 이기고 짝수면 창영이가 이긴다.

•  귀납 가정(N=k일 때)
  • k가 홀수면 상근이가 이긴다.
  • k가 짝수면 창영이가 이긴다.
• 귀납 증명(N=k+1일 때)
  • k+1이 홀수면?
    1. 상근이가 1개를 가져갈 경우 N=k가 되고 k는 짝수 → 창영이는 항상 홀수 개의 돌(k-1 또는 k-3)을 상근이에게 넘기게 된다.
    2. 상근이가 3개를 가져갈 경우 N=k-2가 되고  k+1이 홀수기 때문에 k-2는 짝수 → 이 경우에도 창영이는 항상 홀수 개의 돌(k-3 또는 k-5)를 상근이에게 넘기게 된다.
    3. 홀수 개의 돌이 남은 상태에서 상근이의 턴이 돌아오면 상근이는 홀수 개를 전부 가지고 오면 되기 때문에 무조건 이기게 된다.
  • k+1이 짝수면?
    1. k+1이 홀수인 경우와 동일한 로직으로 동작해 창영이가 무조건 이기게 된다.

 

2-2) 수학 - 전체 코드

N = int(input())

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

 

3-1) DP - 아이디어 흐름 및 코드

① DP 테이블 정의 및 초기값 채우기

개인적으로 DP 유형을 풀 때 가장 중요한 부분은 DP 테이블을 정의하는 것이라고 생각한다. DP 테이블을 적절한 값으로 채울 수 있어야 이걸 활용해서 문제를 풀 수 있기 때문에..! 하지만 이 문제는 설명도 굉장히 짧고, DP를 쓰지 않아도 풀 수 있는 방법이 있어서 그런가 DP 테이블을 어떻게 구성해야 할지 도무지 감이 오지 않았다.

 

백준 질문 게시판을 둘러보는데 '이 문제가 왜 DP인지 모르겠다'는 유저가 몇 분 있었고 힌트를 주는 분이 있어서 그 내용을 참고했다.

 

1개 이상 k개 이하의 돌을 가져가는 게임이 있다고 할 때,
일반적으로 게임 이론에서의 DP 테이블은 아래와 같이 정의할 수 있다.

DP[i] = i번째 돌이 남았을 때, 선공 플레이어가 승리할 수 있는가?

출처: https://www.acmicpc.net/board/view/151649

 

dp = [0]*1001

# dp[i]: 돌이 i개 남아 있을 때 상근이가 이길 수 있는지 체크
dp[1], dp[2], dp[3] = True, False, True

 

위 내용이 굉장히 큰 힌트였기 때문에 저걸 바탕으로 boolean형의 DP 테이블을 정의했다.

 

② 점화식 유도

for i in range(4, 1001):
    if not dp[i-1] or not dp[i-3]:
        dp[i] = True

 

• if not dp[i-1] or not dp[i-3]
  • 돌이 i개 남았을 때 상근이가 이기려면 돌이 i-1개 남았을 때나 i-3개 남았을 때 상근이가 이길 수 없는 상황이면 된다.
  • i=5라고 가정
    1. 돌이 4개(i-1) 남았을 때나 돌이 2개(i-3) 남았을 때 마지막 돌을 창영이가 가져가면 i=5일 때 상근이는 무조건 이길 수 있다.

 

3-2) DP - 전체 코드

N = int(input())

dp = [0]*1001

# dp[i]: 돌이 i개 남아 있을 때 상근이가 이길 수 있는지 체크
dp[1], dp[2], dp[3] = True, False, True

for i in range(4, 1001):
    if not dp[i-1] or not dp[i-3]:
        dp[i] = True

if dp[N]:
    print("SK")
else:
    print("CY")

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 문제는 금방 풀었지만 DP를 어떻게 적용할 수 있을지 생각해내는 게 어려웠다.

❗ 배운 점

• DP 테이블의 값이 무조건 숫자일 필요가 없다. 상황에 맞게 적절히 설정하면 되는데 이건 연습을 많이 해봐야 바로 캐치할 수 있을 것 같다.