사용자 도구

사이트 도구


ps:problems:boj:20903

Confined Catching

ps
링크acmicpc.net/…
출처BOJ
문제 번호20903
문제명Confined Catching
레벨골드 1
분류

게임 이론

사용한 언어Python 3.13
제출기록13816KB / 40ms
최고기록40ms
해결날짜2026/02/24

풀이

  • 돌 A는 상대와 같은 세로줄에, 돌 B는 상대와 같은 가로줄에 놓여 있는 상태를 생각해보자
  • 이 상태에서는 상대가 가로방향으로 이동하면 돌 A,B 모두 가로방향으로 이동하고, 상대가 세로로 이동하면 역시 돌 A,B 모두 세로방향으로 이동하는 전략을 생각할수 있다. 가로 방향으로 이동하면, A는 상대와의 거리가 유지되지만, B는 상대와 점점 가까워지게 된다 (상대가 처음에는 거리를 유지하며 도망갈수 있지만 결국 벽에 막히게 되므로). 마찬가지로 세로 방향으로 이동하면 A와 상대와의 거리가 줄어든다. 어느쪽으로 이동하든 거리가 줄어드므로 결국은 잡히게 된다.
  • 그렇다면, 돌 A는 상대와 같은 세로줄에, 돌 B는 상대와 같은 가로줄에 오도록 이동한 뒤에, 위의 전략을 쓰면 이길수 있다!
  • 그리고 A와 B를 같은 가로/세로줄로 이동시키려고 보면, 사실 그 이후에 움직이는 방법과 동일한 움직임을 사용한다!
    • A는 상대와 x좌표가 다르면 x좌표의 차이가 작아지는 방향으로, x좌표가 같다면 y좌표의 차이가 작아지는 방향으로 움직인다
    • B는 상대와 y좌표가 다르면 y좌표의 차이가 작아지는 방향으로, y좌표가 같다면 x좌표의 차이가 작아지는 방향으로 움직인다
    • 이렇게 하면, 위에서 말한 전략이 다 구현된다.

코드

"""Solution code for "BOJ 20903. Confined Catching".

- Problem link: https://www.acmicpc.net/problem/20903
- Solution link: http://www.teferi.net/ps/problems/boj/20903

Tags: [game theory]
"""

from teflib import psutils


def main():
    _n = int(input())
    x1, y1, x2, y2 = [int(x) for x in input().split()]

    while True:
        x, y = [int(x) for x in input().split()]

        if x == y == 0:
            break

        if x1 != x:
            x1 += 1 if x1 < x else -1
        else:
            y1 += 1 if y1 < y else -1

        if y2 != y:
            y2 += 1 if y2 < y else -1
        else:
            x2 += 1 if x2 < x else -1

        psutils.iprint(x1, y1, x2, y2)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
C S S A Q
 
ps/problems/boj/20903.txt · 마지막으로 수정됨: 2026/02/24 14:12 저자 teferi