[백준, 9655번] 돌 게임 (다이나믹 프로그래밍, DP, Java)

문제설명

입력 & 출력

나의 풀이

이번 "백준 - 돌 게임"문제는 2명의 플레이어(상근,창영)가 돌을 1개 또는 3개 가져갈 때 마지막 돌을 가져가는 사람이 승자하는 게임입니다.

 

규칙을 정리하자면 다음과 같습니다.

1. 돌이 N개 있다.
2. 상근이와 창영이가 번갈아 가며 돌을 가져간다.
3. 각 턴에 1개 또는 3개를 가져갈 수 있다.
4. 마지막 돌을 가져가는 사람이 승리한다.
5. 상근이가 먼저 시작한다.

이번 문제는 동적 계획법 (Dynamic Programming)알고리즘을 사용하여 풀 수 있습니다.

[Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기

 

동적 계획법(이하 DP)는 먼저 배열과 점화식을 만들어야 합니다. 제가 풀이한 동적 계획법 풀이 접근은 다음과 같습니다.

 

1. 배열 정의 

 

• dp[i]
  • 돌이 i개 남았을 때, 상근이가 이기는지 여부를 나타냄.
• dp[i]
  • true면 상근이가 이기고, dp[i]=false면 창영이가 이깁니다.

 

2. 점화식

• dp[i]는 상근이가 한 번의 선택(1개 또는 3개를 가져감)으로 상대방이 지는 상태를 만들 수 있으면 승리합니다.

점화식 : dp[i]= !dp[i−1] || !dp[i−3]

 

3. 초기값 설정

 

• dp[1]=true
  • 돌이 1개일 때 상근이가 가져가서 이김.
• dp[2]=false
  • 돌이 2개일 때 창영이가 이김 (상근이가 돌 1개를 가져가면 창영이가 나머지를 가져가므로).
• dp[3]=true
  • 돌이 3개일 때 상근이가 가져가서 이김.
• dp[4]=false
  • 돌이 4개일 때 상근이가 1개 가져가면 나머지 3개를 가져갈 수 있으므로 창영이가 이김
  • 상근이가 3개를 가져가면, 마지막 남은 돌 1개를 창영이가 가져가기 때문에 창영이가 이김

 

4. 최종 결과

• dp[N]이 true면 상근이가 이기고, false면 창영이가 이깁니다.

---

 

돌이 5개가 있을 때 경우의 수는 위와 같습니다. 

전체 코드

점화식

• dp[i]=!dp[i−1]
  • (상근이가 돌 1개를 가져가서 상대방이 지는 상태를 만들 수 있는 경우)
• dp[i]=!dp[i−3]
  • (상근이가 돌 3개를 가져가서 상대방이 지는 상태를 만들 수 있는 경우)

 

이번 문제에서 !가 사용된 이유는, 상근이가 돌을 가져간 후 상대방이 진다면 상근이가 이긴다는 게임의 특성 때문입니다.

 

따라서 상근이를 기준으로 상근이가 이길 수 있는 상황을 만들기 위해서 상대방(창영)이 이길 수 없는 경우를 찾기 위해 dp[i]=!dp[i−1] || !dp[i−3] 식을 사용한 것입니다.

 

즉, 홀수 개의 돌일 경우 상근이가 이기기 위해, 상대방이 이길 수 없는 상황을 찾기 위해 ! 연산자를 사용하여 true를 만들어 주는 것입니다.