[Python] 24553. 팰린드롬 게임

문제

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

24553번: 팰린드롬 게임

 

---

풀이 과정

시간제한을 보고 구현은 아니겠다고 생각했는데, 그리디 방법을 찾는 것에 시간이 걸렸다.

그것은 주어진 돌의 개수 n이 10의 배수인지 아닌지로 바로 판단할 수 있다. 

• n이 10의 배수인 경우는 승우가 아무리 머리를 쓰더라도 상윤이가 이기게 된다. 
  • 예) n = 10 / 승: 9(승우가 몇 개를 가져와도 나머지가 생김) / 상윤: 1  ➡︎ 상윤 승
  • 예) n = 20 / 승: 8 / 상윤: 2 ➡︎ n = 10이 되므로 상윤 승 
  • 예) n = 100 / 승: 77 / 상윤: 3 ➡︎ n = 20이 되므로 상윤 승

• n이 10의 배수가 아닌 경우에는 승우가 무조건 이기게 된다.
  • n이 한자리 수인 경우, 승우가 다 가져갈 수 있으므로 승우 승
  • 예) n = 98 / 승: 8 ➡︎ n = 90으로 10의 배수가 되었으므로 승우 승

승우와 상윤이는 항상 최선의 수만 둔다고 했으므로,
따라서 남은 돌의 수를 10의 배수가 되도록 만드는 사람이 이기게 된다. 

 

---

코드

t = int(input())
for _ in range(t):
    n = int(input())    # 돌의 개수

    # 순서 : 승우(0) -> 상윤(1)
    if n % 10:
        print(0)
    else:
        print(1)