[BOJ] 백준 9732번 : Division Game (JAVA)

문제

Division game is a 2-player game. In this game, there is a matrix of positive integers with N rows and M columns.

 

Players make their moves in turns. In each step, the current player selects a row. If the row contains all 1s, the player loses.

 

Otherwise, the player can select any number of integers (but at least 1 and each of them should be greater than 1) from that row and then divides each of the selected integers with any divisor other than 1.

 

For example, 6 can be divided by 2, 3 and 6, but cannot be divided by 1, 4 and 5. The player who first makes the matrix all 1s wins.

 

In other words, if in his/her move, player gets the matrix with all 1s, then he/she looses. Given the matrix, your task is to determine whether the first player wins or not. Assume that both of the players will play perfectly to win.

 

 

입력

The first line has a positive integer T, T <= 100,000, denoting the number of test cases.

 

This is followed by each test case per line. Each test case starts with a line containing 2 integers N and M representing the number of rows and columns respectively.

 

Both N and M are between 1 and 50 inclusive. Each of the next N line each contains M integers. All these integers are between 2 and 10000 inclusive.

 

 

출력

For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is “YES” when the first player has a winning strategy and “NO” otherwise.

 

 

풀이

간단한 수학 지식과 님게임의 필승 법칙을 사용하여 풀 수 있는 문제였습니다.

 

 

문제가 조금 이해하기 난해했는데, 행을 하나 고르고 임의의 정수를 선택한 뒤, 각각 1 이상의 수로 나누어주는 방식의 게임이었습니다.

 

이 때, 임의의 정수는 여러 개 선택이 가능하고, 각자 1 이상의 다른 값으로 수로 따로 따로 나누어도 됩니다.

 

예를 들어, 한 행에 수가 "3 4 5"가 있다면, 3은 3으로 나누고, 4는 2로 나누고, 5는 5로 나누는 것이 가능하다는 의미입니다.

 

또한, 특정 수는 1을 제외하고 반드시 나누어떨어지는 수로 나누어야 합니다. 가령, 6은 2, 3 또는 6으로 나누어야하는 것이지, 4로 나누면 안 됩니다.

 

 

여기까지 문제 설명이었고, 각각의 수를 각자 다른 값으로 나눌 수 있다고 하였으므로 한 행에 대해서 소인수분해를 처리하면 님게임과 같게 됩니다.

 

엥? 이게 무슨 말이냐고요? 예를 들어 봅시다.

 

 

한 행에 수가 "3 4 5"라고 가정해 봅니다.

 

그렇다면, 3 = 3 이고, 4 = 2²이고, 5 = 5 입니다. 즉, 거듭제곱의 수가 총 4개이고, 이것을 님게임에 대입하여 생각하면 돌이 4개인 돌무더기와 같습니다.

 

어차피 한 사람이 한 행의 수를 1개든, 2개든, 마음대로 골라서 마음대로 나눌 수 있기때문에 님게임과 규칙이 같아지는 것이죠.

 

따라서, 각 행에 대해서 소인수분해를 한 뒤, 거듭제곱의 수를 싹 더한 다음, 각각의 행에서 구한 거듭제곱 수의 합끼리 XOR합 연산을 하면 됩니다.

 

이 때, XOR합이 0이면 후공이 이기고, XOR합이 0이 아니면 선공이 이기도록 출력하면 끝입니다.

 

 

끝일줄 알았는데, 소인수분해를 할 때 주의할 점이 있습니다.

 

먼저, 문제에서 입력 조건은 "All these integers are between 2 and 10000 inclusive."라고, 2 이상 10000 이하라고 명시해 주었습니다.

 

그렇다는 소리는 1은 들어오지 않는다는 의미이므로 아래처럼 소인수분해 메소드를 정의할 수 있습니다.

 

 

 

 

하지만 이런 식으로 제출하면 틀립니다. 왜냐하면 문제의 입력 조건이 잘못되었기 때문이죠.

 

이 함수에서 n이 1일 때는 'return 0;' 코드를 추가해야 맞게 돌아갑니다.

 

제가 혹시 몰라서 입력을 받을 때 입력값이 1이면 오류를 내 뱉는 출력문을 작성하고 제출했는데 "출력 초과"가 발생하는 것을 보고 확신했습니다.

 

따라서 이 부분에 유의하셔서 소스코드를 작성하시면 되겠습니다.

 

또한, 제가 백준 게시글에 이 공식 문제의 입력과 출력 파일을 올려두었는데, 관심 있으신 분은 이곳을 클릭해 주시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.