코딩 테스트

[HackerRank] Tower Breakers

juble 2024. 10. 30. 13:40

Problem

Two players are playing a game of Tower Breakers! Player 1 always moves first, and both players always play optimally.The rules of the game are as follows:

  • Initially there are n towers.
  • Each tower is of height m.
  • The players move in alternating turns.
  • In each turn, a player can choose a tower of height x and reduce its height to y, where 1≤y<x and y evenly divides x.
  • If the current player is unable to make a move, they lose the game.

Given the values of n and m, determine which player will win. If the first player wins, return 1. Otherwise, return 2.

 

Example. n=2, m=6

There are 2 towers, each 6 units tall. Player 1 has a choice of two moves:
- remove 3 pieces from a tower to leave 3 as 6 modulo 3 = 0
- remove 5 pieces to leave 1

Let Player 1 remove 3. Now the towers are 3 and 6 units tall.

Player 2 matches the move. Now the towers are both 3 units tall.

Now Player 1 has only one move.

Player 1 removes 2 pieces leaving 1. Towers are 1 and 2 units tall.
Player 2 matches again. Towers are both 1 unit tall.

Player 1 has no move and loses. Return 2.

 

Function Description

Complete the towerBreakers function in the editor below.

towerBreakers has the following paramter(s):

  • int n: the number of towers
  • int m: the height of each tower

Returns

  • int: the winner of the game

Input Format

The first line contains a single integer t, the number of test cases.
Each of the next t lines describes a test case in the form of 2 space-separated integers, n and m.

Constraints

  • 1 ≤ t ≤ 100
  • 1 ≤ n, m ≤ 10^6

Sample Input

STDIN   Function
-----   --------
2       t = 2
2 2     n = 2, m = 2
1 4     n = 1, m = 4

Sample Output

2
1

Explanation

We'll refer to player 1 as P1 and player 2 as P2

In the first test case, P1 chooses one of the two towers and reduces it to 1. Then P2 reduces the remaining tower to a height of 1. As both towers now have height 1, P1 cannot make a move so P2 is the winner.

In the second test case, there is only one tower of height 4. P1 can reduce it to a height of either 1 or 2. P1 chooses 1 as both players always choose optimally. Because P2 has no possible move, P1 wins.

두 명의 플레이어가 "타워 브레이커"라는 게임을 하고 있습니다. 플레이어 1이 항상 먼저 시작하며, 두 플레이어는 모두 최선의 선택을 하려고 합니다. 게임 규칙은 다음과 같습니다:

  1. 처음에 높이가 m인 타워가 개 있습니다.
  2. 플레이어는 번갈아가며 자신의 턴에 하나의 타워를 선택해 높이를 줄입니다.
  3. 각 턴에서 플레이어는 높이가 x인 타워를 선택하여, 높이를 y로 줄일 수 있습니다. 이때, 1≤y<x 이고 y는 x를 나누어 떨어져야 합니다 (즉, x%y==0).
  4. 현재 플레이어가 더 이상 움직일 수 없는 상황이 되면, 해당 플레이어는 게임에서 패배하게 됩니다.

주어진 n과 의 값으로 어떤 플레이어가 이길지 결정하는 함수를 작성해야 합니다. 만약 플레이어 1이 승리한다면 1을 반환하고, 플레이어 2가 승리한다면 2를 반환합니다.

예제

  1. 예제 입력: n=2,m=6
    • 6 높이의 타워 두 개가 있습니다. 플레이어 1이 타워 중 하나를 높이 3으로 줄입니다.
    • 이후 플레이어 2가 남은 타워도 높이 3으로 맞춥니다.
    • 이런 식으로 진행하여, 플레이어 1이 더 이상 움직일 수 없는 상황이 되고 플레이어 2가 승리합니다.
    • 출력: 2
  2. 예제 입력: n=1,m=4
    • 플레이어 1이 타워를 높이 1로 줄입니다.
    • 플레이어 2는 움직일 수 없기 때문에 패배합니다.
    • 출력: 1
반응형
728x90

Solution

public static int towerBreakers(int n, int m) {
    // 높이가 1인 경우, 모든 타워가 더 이상 줄일 수 없기 때문에 플레이어 2가 승리
    if (m == 1) return 2;
    // 타워의 개수가 짝수일 경우, 두 플레이어가 번갈아 가며 동일한 높이를 유지하기 때문에 플레이어 2가 승리
    // 타워의 개수가 홀수일 경우, 첫 번째 플레이어가 이길 수 있는 전략을 가짐
    return (n % 2 == 1) ? 1 : 2;
}

 

  1. 타워의 높이가 1인 경우: 모든 타워가 높이 1이라면, 플레이어는 타워 높이를 줄일 수 없어서 그 즉시 턴을 넘기게 됩니다. 이 경우 플레이어 1이 아무런 움직임을 못하고 바로 패배하게 되므로, 결과는 항상 플레이어 2의 승리입니다.
  2. 타워의 개수와 전략:
    • 타워 개수가 홀수일 때는 플레이어 1이 첫 번째 턴에서 타워 하나를 선택하여 전략적으로 움직일 수 있습니다. 이때, 플레이어 1이 먼저 최적의 방법으로 타워를 조절하면, 최종적으로 플레이어 1이 이기는 게임 흐름을 만들 수 있습니다.
    • 타워 개수가 짝수일 때는 두 플레이어가 각 턴마다 서로 같은 방식으로 대응할 수 있어서, 최적의 경우의 수를 생각하면 플레이어 2가 이기는 상황을 만들 수 있습니다.

나는 처음에 for(int i=0; i<n; i+){ 이런식으로 써서 x를 y로 나눴을 때 나머지가 0인지 이런것도 비교하면서 코드를 작성해야하는 줄 알았다. 사실 이 문제는 겉보기에는 복잡한 계산이 필요할 것처럼 보이지만, 게임의 최적 플레이 전략을 이해하면 훨씬 간단하게 해결할 수 있다. 

따라서, 각 타워의 높이를 일일이 나누어 계산하지 않고도 타워 높이가 1인 특수 케이스와 타워 개수의 홀짝성만으로 승자를 결정할 수 있다. 그래서 if (m == 1) return 2;와 return (n % 2 == 1) ? 1 : 2; 같은 간단한 조건문만으로도 답을 구할 수 있게 된다. 

 

728x90
반응형