백준 24553번: 팰린드롬 게임

https://www.acmicpc.net/problem/24553

24553번: 팰린드롬 게임

 

풀이

20~30정도까지 누가 이기는지 적다보면 '어? 10의 배수면 상윤이가 지고 아니면 상윤이가 이기겠네?'하는 감이 올 것이다. '10의 배수이면 상윤이가 지고, 아니면 상윤이가 이긴다'를 1~10*N에 대해서 증명하면 된다. 

수학적 귀납법으로 증명하도록 한다.

1) N==1일 때: 성립한다

2) 임의의 자연수 M에 대하여 1~10*M에서 10의 배수일때만 상윤이가 진다고 가정하면, 10*M+1, 10*M+2, ... , 10*M+9에 경우에서 상윤이가 각각 1, 2, 3, ... , 9개를 가져가면 상대방(즉, 승우)이 지는 상태가 온다. 10*(M+1)에서 상윤이가 이기려면 돌을 10*N(where N <= M)개로 맞춰야 하는데, 10의 배수인 팰린드롬은 없기에 상윤이는 질 수밖에 없다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            System.out.println((Long.parseLong(br.readLine())%10 == 0)? 1: 0);
        }
    }

}