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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWFPoj1qANoDFAV0

SW Expert Academy

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Solution {
    static long N;
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= tc; t++) {
            sb.append("#").append(t).append(" ");
            N = Long.parseLong(br.readLine());
            sb.append(getAnswer()).append("\n");
            //System.out.println(name);
        }
        System.out.println(sb);
    }
 
    private static String getAnswer() {
        while (N > 3) {
            N = N / 2 + 1; //A가 이기기 위해
            N = N / 2 - 1; //B가 이기기 위해
        }
        if(N == 0 || N >= 2)
            return  "Alice";
        else
            return "Bob";
    }
}

풀이

A와 B는 항상 최선을 다한다.

• A가 이기기 위해서는 B가 무조건 N을 초과하는 수를 부르게 해야 함
  • 즉, A가 N/2+1을 부른다면 A의 승리
• B는 A가 N/2 + 1을 부를 수 없도록 (N/2+1)/2 - 1을 불러 A가 최대 N/2 - 1까지만 부르게 함

즉, A가 N/2 + 1을 부르면, 그 대응으로 B는 계속 N(앞서 A가 부른 수)/2 -1 을 부를 것이라는 것

→  이때 A를 Alice, B를 Bob이라고 고정해놓자. 그리고 그렇게 N을 계속 줄여나가며, 특정 수에 도달할 때 까지 반복한다

     - 특정 수 = 0, 2, 3 (Alice가 확정적으로 부르는 수)에 도달할 수 있다면 Alice의 승리, 그렇지 못하면 Bob의 승리

     - 만약 1이라면 Bob의 승리

 

 

 

 

참고

https://heo-it-til.tistory.com/entry/SWEA-D4-%EC%8A%B9%EC%9E%90-%EC%98%88%EC%B8%A1%ED%95%98%EA%B8%B03459-Python