leetcode 1510) Stone Game IV

LV. Hard 🥵

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

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.

Given a positive integer n, return true if and only if Alice wins the game otherwise return false, assuming both players play optimally.

 

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

 

Constraints:

• 1 <= n <= 10^5

 

문제 해결법

n 값 전까지의 i * i의 값을 nums에 저장해줬다.

그리고 1 ~ n까지 거슬러 가면서 결과값을 찾아줬다.

 

n = 1일 때 1(A) → true
n = 2일 때 1(A) - 1(B) → false
n = 3일 때 1(A) - 1(B) - 1(A) → true
n = 4일 때 4(A) → true

n = 3일 때는 1과 2의 조합으로 3을 찾을 수 있다.

1과 2의 조합은 어떻게 나왔냐면 nums의 저장한 제곱근의 값으로 나눈 값이다.

 

예를 들어 7의 조합을 찾을 때는 (1, 6), (2, 5), (3, 4)가 나올 수 있는데 이런 식으로 찾게 되면 optimally 한 값을 찾을 수 없다.

그렇기에 nums에 저장된 제곱근들이 포함된 값으로 조합을 만들어줘야 된다. (제곱근은 무조건 베스트 값이기 때문)

7의 조합을 다시 만들면 (1, 6), (3, 4)가 된다.

 

이런 식으로 조합을 만들어서 두 조합 간의 XOR값을 찾으면 n의 결과값을 구할 수 있다.

 

해결 코드

class Solution {
private:
	vector<bool> list;
	vector<int> nums;
	int max_index;

	void set_list(int n)
	{
		int num = 2;
		max_index = 0;
		nums.push_back(1);
		while (1)
		{
			int temp = pow(num, 2);
			if (temp > n)
				break;
			max_index++;
			list[temp] = true;
			nums.push_back(temp);
			num++;
		}
	}

public:
	bool winnerSquareGame(int n) {
		int left;
		int right;
		bool ans;
		int index;

		list.assign(n + 1, false);
		set_list(n);
		list[0] = false; // list[0]
		list[1] = true;  // list[1]
		list[2] = false; // list[2]

		for (int i = 2; i <= n; ++i) {
			index = 0;
			ans = false;
			left = nums[index];
			right = i - left;
			while (right > 0 && !list[i]) {
				ans = list[left] ^ list[right];
				list[i] = list[i] || ans;
				if (++index > max_index)
					break;
				left = nums[index];
				right = i - left;
			}
		}
		return list[n];
	}
};