[Python] 1459번 걷기

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

---

 

25/06/13

 

 

무난 무난한 기하학 + 애드 혹 문제이다. 약간의 케이스워크가 있는데, 잘 정리하면 케이스워크도 쉽게 정리할 수 있다.

---

 

문제 접근 방식:

 

 

문제는 가로, 세로로 가는 데 걸리는 시간과 대각선으로 가는데 걸리는 시간이 따로 주어지고, 양수 좌표 $x, y$가 따로 주어질 때 $(0, 0)$에서 해당 좌표로 갈 수 있는 최단 시간을 출력하는 것이다.

 

결국 세가지 경우로 나뉜다.

 

1. 가로, 세로 움직임만 사용하여 가는 경우

 

2. $x = x_0, y = y_0$를 벗어나지 않는 선에서 대각선 움직임을 최대한 사용한 후 가로, 세로 움직임을 사용하여 가는 경우

 

3. 벗어나도 상관없이, 대각선 움직임을 최대한 사용하여 가는 경우

 

1번과 2번은 납득이 될 만한데, 3번이 무슨 말인지 잘 모를 수도 있을 것이다.

 

예를 들어, $(2, 0)$을 가야되는데, 대각선 움직임은 $10$, 가로세로 움직임은 $12$가 든다고 치면, 대각선으로 두 번 움직여서 갈 수 있다.

 

이 경우 움직이는 최소 시간이 $20$이 된다.

 

이처럼 $(0, 0)$과 $(x, y)$를 양 끝 꼭짓점으로 가지는 직사각형을 벗어나는 범위의 움직임이지만, 최소 시간을 가질 수 있다.

 

$x+y$가 짝수인 경우, 3번 경우는 대각선으로만 움직일 수 있는 케이스가 되고, 이 경우 $\max (x, y)$번 만큼 대각선 움직임이 된다.

 

$x+y$가 홀수인 경우, $\min (x, y)$만큼 대각선으로 움직인 후에, 직선으로 $2$칸 가는 대신 대각선으로 $2$칸 가는 것으로 대체해서 움직이면 된다. 즉, $\min (x, y) + |x-y|//2$번 만큼 대각선으로 움직이고, 그 이후에 모자라면 직선으로 움직이면 된다.

 

따라서 케이스는 $x+y$가 홀/짝인 경우만 나누면 되고, 1번과 2번의 경우 홀/짝의 경우 모두 동일하므로 $\min$값을 잘 취해줘서 출력해주면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1459번 걷기
import sys
input = sys.stdin.readline

X, Y, W, S = map(int, input().split())
if (X+Y) % 2 == 0:
    print(min(W*(X+Y), min(X, Y)*S + abs(X-Y)*W, max(X, Y)*S))
else:
    print(min(W*(X+Y), min(X, Y)*S + abs(X-Y)*W, min(X, Y)*S + (abs(X-Y)//2)*2*S + (abs(X-Y)%2)*W))