[JAVA][SWEA] 3459. 승자 예측하기

N이 주어질 때, 두 사람이 최선을 다해 게임을 한다면 어떤 사람이 이기게 되는지 출력하는 프로그램을 작성하라.

이 문제에서 가장 힘들었던 점이 최선을 다해 게임을 한다면 이었다.

처음에 모든 경우를 종이에 적어 구해보았는데 숫자가 작은 수부터 시작한다면 

경우의 수가 너무 많아지고 계산식이 복잡해 지는 것을 확인하고 역으로 N부터 시작해보았다.

예를 들어 N이 100일때

1. 내가 이기기 위해서는 다음 사람이 무조건 100 "초과" 하는 숫자를 부르게 해야함으로 

내가 51 을 부르면 다음 사람은 최소 102를 부르게 되므로 무조건 이길 수 있다.

2. 반대로 그렇다면 나의 상대는 내가 51을 부를 수 없도록 24라는 숫자를 불러

내가 최대 49의 숫자를 부를 수 밖에 없게 만든다.

이 두가지를 반복하게 되면

서로 최선을 다했을때 51 24 13 5 3 .... 라는 순서가 오게된다. 

이때 3이라는 숫자는 엘리스만 부를 수 있으므로 엘리스의 승리이다.

잘 이해가 되지 않는 다면 역으로 이 생각을 작은 순서부터 작성해보면 이해가 빠를 것이다.

N이 100일때 엘리스가 3만 부르게 되면 밥이 무었을 내든 

엘리스가 그 상황에 대해 적절한 조치를 취한다면 무조건 엘리스가 승리한다.

소스 코드는 간단하지만 다음과 같다.

( 단, 작성자는 초반에 모든 수를 계산해 보느라 약 1~25정도의 수는 누가 이기게 되는지 미리 계산을 한 상태이다. )

package D4;
 
import java.io.*;
 
public class D4Solution3459 {
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++) {
            long N = Long.parseLong(br.readLine());
            String s = "Alice";
            while(N > 10) {
                N = (N/2) + 1;
                N = (N/2) - 1;
            }
            if( N == 1 || (N >= 6 && N <= 9)){
                s = "Bob";
            }
            bw.write("#"+t+" "+s+"\n");
        }
        br.close();
        bw.close();
    }
 
}