[C++] 백준 9655번 풀이 (돌 게임)

- 문제 (9655번) : 돌게임

• 링크 : https://www.acmicpc.net/problem/9655

• 상근이와 창영이가 턴을 번갈아가며 1개 또는 3개의 돌을 가져가는데 마지막 돌을 가져가는 사람이 누구인지 구하는 문제.
  (돌의 개수는 입력받는 N, 출력되는 이름의 사람이 돌게임의 승자)

---

- 입력 및 출력

[입력]

• 첫째줄에 돌의 개수 N 입력

[출력]

• 마지막 돌을 가져가는 사람 즉, 승자의 이름을 출력
  ( 상근 : SK, 창영 : CY 를 출력)

---

- 문제 풀이

• 이 문제는 2가지 방법으로 풀 수 있다.

1. 돌의 개수가 홀수인지 짝수인지 판별
   • 이 문제는 간단히 게임을 실시하는 돌의 개수로 승자를 판별하는 문제이다.
   • 한사람이 한 턴당 가져갈 수 있는 돌의 개수는 1개 또는 3개로 홀수개의 돌만을 가져갈 수 있기 때문에 돌의 개수가 홀수인지 짝수인지로 승자를 가릴 수 있다.
     

2. 다이나믹 프로그래밍 이용

   • memoization을 이용해 돌을 가져가는 횟수로 승자를 판별하는 방법

   • 돌을 가져가는 횟수가 홀수면 먼저 시작한 상근 win
     돌을 가져가는 횟수가 짝수면 나중에 시작한 창영 win

   • 게임을 진행할 때 기본적으로 1개의 돌을 가져가고, 돌의 개수가 3개 이상이 있을 때 3개씩 가져가면 돌을 가져가는 횟수가 홀/짝 인지에는 영향없이 게임이 빠르게 진행된다.

   • 따라서 recurrence relation은 다음과 같은 식을 따른다.
     (i개의 돌이 있을 때 돌을 가져가는 총 횟수 : arr[i])

     arr[i] = Min((arr[i-3] + 1), (arr[i-1] + 1))
     -> 1개씩 가져간다면 직전 횟수 +1
     -> 3개씩 가져간다면 3번째 단계 전 횟수 + 1

---

- 최종 코드

1. 돌의 개수가 홀수인지 짝수인지 판별
   

2. 돌을 가져가는 횟수가 홀수인지 짝수인지 판별
   

---

- 참고자료

블로그 : https://beginnerdeveloper-lit.tistory.com/83