1510. Stone Game IV / TypeScript

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).

 

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

 

 

풀이

function winnerSquareGame(n: number): boolean {
    const res: boolean[] = new Array(n + 1).fill(false);
    let k: number = 1;
    
    for (let i: number = 1; i <= n; i++) {
        if (k * k === i) {
            res[i] = true;
            k++;
            continue;
        }
        
        for (let j: number = 1; j < k && j * j <= i; j++) {
            if (!res[i - j * j]) {
                res[i] = true;
                break;
            }
        }
    }
    
    return res[n];
}

 

Alice와 Bob이 각각 번갈아가며 돌을 제거하는 게임.

Alice는 먼저 시작하고, 주어진 돌의 개수에서 제곱수를 제거. 즉, 매 턴마다 플레이어는 1, 4, 9, 16과 같은 제곱수를 선택해 해당 개수만큼의 돌을 가져감.

이 게임에서 Alice가 이기려면, 남은 돌이 없을 때 Bob의 턴이 되어야 함.

Alice가 최선의 선택을 한다고 가정했을 때, Alice가 승리할 수 있는지를 판단하는 문제

 

게임 규칙:

1. 초기 상태: 게임은 n개의 돌로 시작
2. 차례: Alice와 Bob이 번갈아 가며 돌을 제거/ Alice가 첫 번째로 시작
3. 돌 제거: 각 플레이어는 자신의 차례에 돌무더기에서 제곱수만큼의 돌을 제거할 수 있음. 예를 들어, 1, 4, 9, 16 등의 제곱수를 제거할 수 있습니다.
   • 제곱수는 1, 4, 9, 16, 25 등, 정수의 제곱이 되는 수
4. 패배 조건: 만약 차례인 플레이어가 제거할 수 있는 돌의 개수가 없으면, 그 플레이어는 패배

풀이 과정:

1. res 배열의 역할: res 배열은 각 돌의 개수에 대해 Alice가 이길 수 있는지를 저장.
   1. res[i]가 true이면 Alice가 i개의 돌이 있을 때 이길 수 있다는 의미. false이면 Alice는 해당 돌의 개수에서 패배
2. 초기 값 설정: 배열 res는 n + 1 길이로 생성되며, 모두 false로 초기화.
   1. res[0]은 사용되지 않으며, res[i]는 Alice가 돌의 개수 i에서 이길 수 있는지 여부를 결정하는 값
3. 루프를 통한 판단: for 루프는 돌의 개수를 1부터 n까지 확인. 각 돌의 개수 i에 대해 Alice가 이길 수 있는지를 계산.
   • 먼저, k * k가 i와 같으면, 즉 i가 제곱수이면 Alice는 항상 이김.
     •  Alice가 한 번에 모든 돌을 제거할 수 있기 때문. 따라서 res[i] = true로 설정하고 다음 돌 개수로 넘어감.
   • 제곱수가 아닌 경우, Alice는 j * j(1 ≤ j < k)만큼 돌을 제거할 수 있음. 이때 남은 돌 개수 i - j * j에서 Bob이 이기는지 확인. 만약 Bob이 해당 돌 개수에서 이길 수 없으면(Alice가 이길 수 있다는 의미), Alice가 승리할 수 있음.
     • 즉, res[i - j * j]가 false인 경우, Alice는 승리할 수 있는 선택을 한 것이므로 res[i]를 true로 설정하고 루프를 종료.
4. 결과 반환: 최종적으로 res[n]의 값이 true이면 Alice가 승리할 수 있다는 뜻이고, false이면 패배한다는 뜻

 

 

n = 4일 때

1.초기화

const res: boolean[] = new Array(n + 1).fill(false);
let k: number = 1;

 

res 배열은 [false, false, false, false, false]로 초기화

 

2. 첫 번째 루프 (i = 1):

• Alice는 돌이 1개인 경우에 게임

if (k * k === i) {
    res[i] = true;
    k++;
    continue;
}

 

• k * k === 1 * 1 === 1, 즉 i가 제곱수이므로 Alice는 돌 1개를 제거하고 승리할 수 있음. 따라서 res[1] = true로 설정
• 이때, res 배열은 [false, true, false, false, false]
• 이후 k++로 인해 k = 2

3. 두 번째 루프 (i = 2):

• 돌이 2개일 때, 제곱수는 아님

for (let j: number = 1; j < k && j * j <= i; j++) {
    if (!res[i - j * j]) {
        res[i] = true;
        break;
    }
}

 

 

 

• 가능한 제곱수는 1^2 = 1이므로 Alice는 1개의 돌을 제거하고, 남은 돌이 2 - 1 = 1
• 남은 돌이 1개인 경우, res[1] = true이므로 Bob이 이길 수 있음. 따라서 Alice는 이길 수 없음
• 결과적으로 res[2]는 여전히 false
• res 배열은 [false, true, false, false, false]로 유지

4. 세 번째 루프 (i = 3):

• 돌이 3개일 때도 제곱수가 아닙

for (let j: number = 1; j < k && j * j <= i; j++) {
    if (!res[i - j * j]) {
        res[i] = true;
        break;
    }
}

 

 

• 가능한 제곱수는 1^2 = 1. Alice는 1개의 돌을 제거하고, 남은 돌은 3 - 1 = 2
• 남은 돌이 2개일 때, res[2] = false이므로 Bob이 이길 수 없음. 따라서 Alice는 이길 수 있음
• res[3] = true로 설정
• 이때, res 배열은 [false, true, false, true, false]

5.네 번째 루프 (i = 4):

• 이번에는 i = 4이므로, 4는 제곱수

if (k * k === i) {
    res[i] = true;
    k++;
    continue;
}

 

 

• k * k === 2 * 2 === 4이므로, Alice는 한 번에 4개의 돌을 모두 제거할 수 있음. 따라서 Alice는 승리
• res[4] = true로 설정
• res 배열은 [false, true, false, true, true]
• 그리고 k++로 인해 k = 3

최종 결과:

• n = 4일 때, res[4] = true이므로 Alice는 4개의 돌이 있을 때 이길 수 있음

결론적으로, n = 4일 때 Alice는 승리할 수 있으므로 함수는 true를 반환