[해커랭크] Stone Division (어쩐지 난이도 Hard였구나)

[해커랭크] Stone Division

Consider the following game:

• There are two players, First and Second, sitting in front of a pile of  stones. First always plays first.
• There is a set, , of  distinct integers defined as .
• The players move in alternating turns. During each turn, a player chooses some  and splits one of the piles into exactly  smaller piles of equal size. If no  exists that will split one of the available piles into exactly  equal smaller piles, the player loses.
• Both players always play optimally.

Given , , and the contents of , find and print the winner of the game. If First wins, print First; otherwise, print Second.

Input Format

The first line contains two space-separated integers describing the respective values of  (the size of the initial pile) and  (the size of the set).
The second line contains  distinct space-separated integers describing the respective values of .

Constraints

•  
•  
•  

Output Format

Print First if the First player wins the game; otherwise, print Second.

Sample Input 0

15 3
5 2 3

Sample Output 0

Second

Explanation 0

The initial pile has  stones, and . During First's initial turn, they have two options:

1. Split the initial pile into  equal piles, which forces them to lose after the following sequence of turns:
   

   

2. Split the initial pile into  equal piles, which forces them to lose after the following sequence of turns:
   

   

Because First never has any possible move that puts them on the path to winning, we print Second as our answer.

 

 

 

 

 

오랜만에 단련이라 그런가,, 문제는 단순하고 쉬워보였으나 정답은 매우 어려웠다.. 챗지피티랑 같이 풀었다

 

정리하자면,

 

- for문 돌면서 divSize로 나눈다. 

- 안나눠 지는 케이스는 continue (1이하이거나 0으로 안떨어지거나 나누지못한경우)

- 그리고 이제 재귀 호출해서 nextStep을 int로 받아둔다. (다음 상태를 상상해봤을때, 상대방 턴으로 나눌 수 있다면 내가 지는거고, 상대방 턴으로 못나눈다면 내가 이기는거라서 받아두는거기 때문)

 

여기가 가장 핵심..

1. 몇덩이로 나눌지에 대한 크기를 나타내는 divSize가 만약 짝수라면

   => 내가 질 확률이 높다. 나뉜 짝수개에서 내가 나눈만큼 상대방도 똑같은 횟수로 나눌 수 있을테니, 그래서 0으로 리턴 (내가 지는 경우가 됨)

2. divSize가 만약 홀수개라면?

   => 내가 나눈만큼 상대방도 똑같은 횟수로 나누고나서도, 1번의 턴이 무조건 남을텐데, 해당 턴의 결과를 그대로 승계해준다.

 

1,2의 케이스에 대한 결과를 xorResult 변수로 받아서

도달 가능한 상태값을 뜻하는 reachable 변수에 모은다.

 

--------------------

 

이렇게 for문이 다 끝나면. reachable 에는 내가 지는 경우인 0만 담겨있다거나, 그렇지 않을텐데

    public static String stoneDivision(long n, List<Long> s) {

        Map<Long, Integer> dp = new HashMap<>();

        return firstCanWin(n, s, dp) != 0 ? "First" : "Second";

    }

에서 호출한 최초의 재귀함수가 0이면 내가 지는거다. 아니면 이기는거고.

지면 0만 모은다. mex라는 변수값을 보면 알다시피 0 초과 값이 있는지 체크.

 

 

 

 

 

이해하는데 있어서 이기는것만 생각했었는데

내가 지는 0만 담기는 상황을 생각하는것도 이해하는데 도움이 됐다.

 

 

 

 

 

 

6
23
테스트 케이스 풀이는 아래와 같다.

테스트케이스

• 돌무더기 크기 n = 6
• 나눌 수 있는 개수 s = {2, 3}

---

가능한 첫 움직임

• 6을 2개로 나누면 각각 크기 3인 무더기 2개
• 6을 3개로 나누면 각각 크기 2인 무더기 3개

---

함수 동작 요약

firstCanWin(6) 호출하면 다음 두 가지 경우를 계산해봐요:

1. divSize = 2 (짝수)
   • 조각 크기: 6 / 2 = 3
   • nextState = firstCanWin(3)
   • xorResult = (2 % 2 == 0) ? 0 : nextState → 0 (짝수니까 무조건 0)
   • reachable 집합에 0 추가
2. divSize = 3 (홀수)
   • 조각 크기: 6 / 3 = 2
   • nextState = firstCanWin(2)
   • xorResult = (3 % 2 == 0) ? 0 : nextState → nextState 그대로
   • reachable 집합에 firstCanWin(2) 값 추가

---

재귀 호출: firstCanWin(3)과 firstCanWin(2)

• firstCanWin(3)
  • 가능한 divSize: 2, 3
  • 3 % 2 != 0 → 불가
  • 3 % 3 == 0 → 나누기 가능 (3 / 3 = 1)
  • firstCanWin(1) 호출 → 기본적으로 1은 더 이상 나눌 수 없으니 0 반환 (패배 상태)
  • divSize 3은 홀수니까 xorResult = firstCanWin(1) = 0
  • reachable = {0}
  • mex는 1 (0은 있으니까 다음 숫자)
  • 따라서 firstCanWin(3) = 1
• firstCanWin(2)
  • 가능한 divSize: 2, 3
  • 2 % 2 == 0 → 나누기 가능 (2 / 2 = 1)
  • firstCanWin(1) 호출 → 0
  • divSize 2는 짝수니까 xorResult = 0
  • 2 % 3 != 0 → 불가
  • reachable = {0}
  • mex = 1
  • 따라서 firstCanWin(2) = 1

---

다시 firstCanWin(6)으로 돌아와서

• reachable = {0, firstCanWin(2)} = {0, 1}
• mex 찾기: mex는 0부터 시작해서 reachable에 있으면 1, 1도 있으면 2
• 0과 1 모두 있으니 mex = 2
• firstCanWin(6) = 2
• 0이 아닌 값인 2가 최종 리턴되니 내가 승리한다

 

 

 

전체 코드는 아래와 같다.

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.function.*;

import java.util.regex.*;

import java.util.stream.*;

import static java.util.stream.Collectors.joining;

import static java.util.stream.Collectors.toList;

class Result {

    /*

     * Complete the 'stoneDivision' function below.

     *

     * The function is expected to return a STRING.

     * The function accepts following parameters:

     *  1. LONG_INTEGER n

     *  2. LONG_INTEGER_ARRAY s

     */

     

    public static int firstCanWin(long n, List<Long> s, Map<Long, Integer> dp) {

        // return exists result

        if (dp.containsKey(n)) {

            return dp.get(n);

        }

        Set<Integer> reachable = new HashSet<>();

        for (long divSize : s) {

            if (divSize <= 1 || n % divSize != 0) {

                continue;   // can not div

            }

           

            long mok = n / divSize;

            if (mok >= n) {

                continue;   // can not div

            }

            int nextState = firstCanWin(mok, s, dp);

           

            // even => 0, odd => nextState

            int xorResult = (divSize % 2 == 0) ? 0 : nextState;

            reachable.add(xorResult);

        }

        // Find mex

        int mex = 0;

        while (reachable.contains(mex)) {

            mex++;

        }

       

        // mex=0 => im lose...

        // mex!=0 => im win!

        dp.put(n, mex);

        return mex;

    }

    public static String stoneDivision(long n, List<Long> s) {

        Map<Long, Integer> dp = new HashMap<>();

        return firstCanWin(n, s, dp) != 0 ? "First" : "Second";

    }

}

// Sprague-Grundy

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        long n = Long.parseLong(firstMultipleInput[0]);

        int m = Integer.parseInt(firstMultipleInput[1]);

        List<Long> s = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))

            .map(Long::parseLong)

            .collect(toList());

        String result = Result.stoneDivision(n, s);

        bufferedWriter.write(result);

        bufferedWriter.newLine();

        bufferedReader.close();

        bufferedWriter.close();

    }

}

 

 

 

 

12번 테스트케이스도 참고하세요