[백준][파이썬] 1459번. 걷기

문제

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

 

풀이

2 * W가 S보다 작거나 같다면, 대각선 이동을 하지 않고 직선 이동만 해서 집에 도달하는 것이 가장 적은 시간이 걸린다.

 

그러나 2 * W가 S보다 크다면 상황이 약간 복잡해진다.

나는 크게 세 가지 경우로 나누어 생각했다.

1. 대각선으로만 이동 가능한 경우
2. 대각선으로 최대한 이동 후, 직선으로 한 번만 이동하는 경우
3. 대각선, 직선 이동을 섞어야 하는 경우

1. 대각선으로만 이동 가능한 경우

(X, Y) 좌표의 합이 짝수라면, 대각선으로만 이동하며 집에 도착할 수 있다.

이 경우 걸린 시간은 S * max(X, Y)가 된다.

2. 대각선으로 최대한 이동 후, 직선으로 한 번만 이동하는 경우

(X, Y) 좌표의 합이 홀수라면, 즉 X와 Y 중 하나는 홀수, 하나는 짝수라면 대각선 이동만으로는 집에 도착할 수 없다.

이 경우에는 (X, Y) 좌표의 합이 짝수인 지점까지 최대한 대각선으로 이동한 후, 남은 하나의 직선을 통하여 집까지 도착할 수 있다.

예를 들어 집의 좌표가 (4, 3)이라면 (3, 3)까지 대각선으로 이동한 후, 거기에서 (4, 3)까지 가로로 이동하면 된다.

3. 대각선, 직선 이동을 섞어야 하는 경우

(X, Y) 좌표의 합이 홀수인지 짝수인지와 관계없이, 대각선 이동과 직선 이동을 섞는 것이 최소 시간으로 집에 도착하는 방법일 수도 있다.

예를 들어 입력이 4 2 3 5로 주어졌을 때,

대각선으로만 이동하면 (0, 0) → (1, 1) → (2, 2) → (3, 3) → (4, 2) 이고, 이때 소요되는 시간은 5 * 4 = 20이지만

대각선과 직선을 섞어서 이동하면 (0, 0) → (1, 1) → (2, 2) → (3, 2) → (4, 2) 이고, 이때 소요되는 시간은 5 * 2 + 3 * 2 = 16이다.

 

2 * W가 S보다 클 때 1, 2, 3번 중 가장 적은 소요시간을 갖는 경우로 계산을 진행하였다.

X, Y, W, S = map(int, input().split())

answer = 0
# 2 * W < S 이면 -> W * (X + Y)
if (2 * W) <= S :
  answer = W * (X + Y)

else :
  temp1, temp2 = 1e9, 1e9
  # 1. 대각선으로만 이동 가능한 경우 -> (X + Y)가 짝수인 경우
  if (X + Y) % 2 == 0 :
    temp1 = S * max(X, Y)
  # 2. X, Y 중 하나는 홀수, 하나는 짝수인 경우 -> (X, Y) 중 큰 숫자 - 1 까지 대각선 이동 후 직선이동 한 번 하기
  else :
    temp1 = S * (max(X, Y) - 1) + W
  # 3. 대각선, 직선이동 섞어야 하는 경우
  temp2 = S * min(X, Y) + W * (X + Y - 2 * min(X, Y))
  answer = min(temp1, temp2)

print(answer)