백준 29774 케이크 자르기 게임 (small) - java 에드훅

자자 가보자

 

A와 B가 케이크를 둘레에서 둘레로 한번씩 자른다. 조각이 K 넘게 자른사람이 케이크 위 맛난 딸기를 냠념냠 가능하다.

따라서 A와 B는 모두 최선을 다해 자신이 K 조각이 넘길 바라며 최선을 다한다.

 

처음에는 규칙을 찾으려고 했었다. 에드 혹 태그가 달려있어서 특별한 자료구조는 필요하지 않겠다 싶었고.

경우의 수들을 나눠봤다.

 

허접해서 죄송합니다 ㅎ히홓훟ㅋㅋ

 

먼저 케이크 둘레에서 둘레를 자르기 때문에 자른 횟수가 N번째인 사람은 조각을 최대 N개를 늘릴 수 있다.

지나친 간선 + 1이 최대이고. 둘레에서 둘레기 때문에 어떻게든 1조각도 늘어날 수 있겠다 생각을 했었다.

 

그렇다면 최선을 다한다만 생각하면 되려나? 였다.

비슷한 게임인 베라31에선 내가 상대방을 이기기 위해 상대방은 나를 못 끝내지만 다음에는 내가 끝내던지. 내가 끝내던지가 중요하다.

 

첫번째 예시는 상대방이 30을 외치면 지므로, 상대방의 최대범위인 28을 주면 안된다. 28 29 30 하고 내가 31하면 지니까..

두번째는 내가 가능한 범위에서는 30을 외치면 이긴다. 상대방이 31을 외치도록.

 

고민을 조금하면 베라31 에서도 필승 공식이 있다.

30을 외치면 이기기에 서로의 범위가 1~3이므로 4의 배수인 30 26 22 18 14 10 6 2를 외친 사람이 이긴다.

한사람이 무엇을 외치던 4의 배수로 맞출 수 있기 때문에 호호

 

위 문제처럼 숫자로 갈려버린다. 이 문제도 그렇게 고민했었다.

범위는 각자 1~N까지이고, 상대방은 1~N+1이라고 가정. 베라31처럼 범위가 생겨난다.

 

 

excel로 대충 짜봤는데 다시 설명하면

먼저 N = 1 이면 최소, 최대 2 고정이다.

이후 N = 2 면 최대에서 + 1 즉 2+1 = 3이 최소범위가 되고, 최소인 2에서 N을 더한 2 + 2 = 4가 최대 범위가 된다.

다음 N = 3 일때 , 최대인 4에서 + 1 즉 4 + 1 = 5가 최소 범위, 최소인 3 + N을 더한 6이 최대 범위가 된다.

 

결국 앞차례 최소 + N 이 다음 차례의 최대 범위이며, 최대 + 1 이 다음 차례에 최소 범위가 된다.

따라서 K의 숫자가 정해짐에 따라 승자가 정해진다.

 

 

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int k = scanner.nextInt();
        int a = 2;
        int b = 2;
        int n = 1;
 
        boolean isAlice = true;
 
        while (true) {
            if (a <= k && k <= b) break; // 최소와 최대 범위에 K가 있다면.
 
            int temp = a;
            a = b + 1;          // 최소범위
            b = temp + (++n); // 최대범위
 
            isAlice = !isAlice;
        }
 
        System.out.println(isAlice ? 'A' : 'B');
    }
}