[BOJ] 백준 13343번 : Block Game (JAVA)

문제

You are attending the International Construction by Preschoolers Contest. Unfortunately, you are too old to participate, but you still enjoy watching the competition.

 

In between rounds, you are walking around the contest area when you see a toddler, one of the contestants, playing with her blocks. Annoyed that she is having all the fun, you decide to challenge her to a game.

 

You set up two stacks of blocks of a certain height. Then, you and the toddler take turns removing some number of blocks from the stack which contains the largest number of blocks (if both stacks have the same number of blocks, the current player can choose either stack to remove blocks from).

 

The number of blocks removed must be a positive multiple of the number of blocks in the smaller stack. For instance, if there is a stack with 5 blocks, and one with 23 blocks, then the current player can remove 5, 10, 15 or 20 blocks from the stack of 23 blocks. The player who empties one of the stacks wins the game.

 

You have graciously decided to take the first move, but then a worry strikes you – might this devious preschooler still be able to beat you?

 

 

입력

One line with two integers N and M, satisfying 1 ≤ N, M ≤ 1018, the initial sizes of the two stacks of blocks.

 

 

출력

Output a single line containing a single word: the word “win” if you are guaranteed to win if you play correctly, and the word “lose” if your opponent can force you to lose.

 

 

풀이

유클리드 호제법과 게임 이론을 이용하여 풀 수 있는 문제였습니다.

 

 

이 문제는 "4342번 유클리드 게임"과 상당히 유사합니다.

두 개의 블록 더미에서 블록을 가져오는데, 작은 블록 더미의 배수가 되도록 큰 블록 더미에서 블록을 빼는 것이기 때문에 유클리드 호제법을 활용해야합니다.

 

 

"4342번 유클리드 게임"과 달리 값이 최대 10^18까지 들어오므로 자료형만 long으로 잘 설정해 주면 나머지는 똑같아서 4342번 문제의 해설 포스팅을 올려놓겠습니다.

 

 

[BOJ] 백준 4342번 : 유클리드 게임 (JAVA)

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

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