🥇

Stone Game IV

Created

2022/01/22 08:02

문제 번호

1510

카테고리

Math

Dynamic Programming

Game Theory

Stone Game IV - LeetCode

Alice and Bob take turns playing a game, with Alice starting first. Initially, there are n stones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile. Also, if a player cannot make a move, he/she loses the game.

https://leetcode.com/problems/stone-game-iv/

Code

제출 날짜	시간	메모리
2022/01/22	32 ms	2.5 MB

// 1510. Stone Game IV
//
// https://leetcode.com/problems/stone-game-iv/

// winnerSquareGame function returns true if Alice wins, false if Bob wins.
// About turn to play the game, Alice always starts first.
// Once Alice wins, it should be makred false to true.
// For example to make number 7, Alice can choose number 1 or 4.
// Then, the result depends on dp[7 - 1] or dp[7 - 4].
// If dp[7 - 1] was false (Alice loses), then dp[7] can be marked as true.
// Also if dp[7 - 4] was false (Alice loses), then dp[7] can be marked as true.
// To get dp[7], dp[7 - 1] and dp[7 - 4] can be done as same way. Thus, every number until input n should be calculated.
// Iteratings on outer loop for 1 to n, and inner loop for square numbers until outer one should be done.
func winnerSquareGame(n int) bool {
	dp := make([]bool, n+1)
	for i := 1; i <= n; i++ {
		for j := 1; j*j <= i; j++ {
			if !dp[i] {
				dp[i] = !dp[i-j*j]
			}
		}
	}
	return dp[n]
}
Go
복사