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()
ps/problems/boj/20903.txt · 마지막으로 수정됨: 2026/02/24 14:12 저자 teferi

토론