[BOJ] 백준 3358번 : Towers of coins (JAVA)

문제

Asen and Boyan are playing the following game They choose two different positive integers K and L, and start the game with a tower of N coins.

 

Asen always plays first, Boyan – second, after that – Asen again, then Boyan, and so on. The boy in turn can take 1, K or L coins from the tower. The winner is the boy, who takes the last coin (or coins).

 

After a long, long playing, Asen realizes that there are cases in which he could win, no matter how Boyan plays. And in all other cases Boyan being careful can win, no matter how Asen plays.

 

So, before the start of the game Asen is eager to know what game case they have. Write a program coins which help Asen to predict the game result for given K, L and N.

 

 

입력

The input describes m games.

 

The first line of the standard input contains the integers K, L and m, 1 < K < L < 10, 3 < m < 50. The second line contains m integers N1, N2, …, Nm, 1 ≤ Ni ≤ 1 000 000, i = 1, 2, …., m, representing the number of coins in each of the m towers.

 

 

출력

The standard output contains a string of length m composed of letters A and B. If Asen wins the ith game (no matter how the opponent plays), the ith letter of the string has to be A. When Boyan wins the ith game (no matter how Asen plays), the ith letter of the string has to be B.

 

 

풀이

간단한 게임 이론 문제였습니다.

 

 

플레이어는 동전 더미에서 1, K, L개 중 하나로 동전을 꺼내올 수 있고, 마지막에 동전을 가져가는 사람이 승리하는 규칙의 게임이었습니다.

 

 

다음 상황에 선공이 지는 상황이 하나라도 있으면, 현재 지는 상황으로 만들어서 후공으로 넘겨주어 선공이 승리할 수 있습니다.

 

따라서, dp[0] = false, dp[1] = true로 초기 세팅을 한 뒤, i = 2부터 시작해서 dp[i - 1], dp[i - K], dp[i - L] 중 false 값이 하나라도 있으면 i번째의 선공은 필승합니다.

 

 

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

 

 

소스코드

 

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