BOJ 1459 - 걷기

문제 링크

그리디 문제이다.

처음에 생각한 것은 위 그림에서 1,2,3의 3가지 방법이 있을 것이라고 생각했다.
하지만 예제 입력 7번은 1,2,3 중 어느 경우에도 해당하지 않았다.
따라서 4번 방법을 떠올리고 문제를 풀었다.

x <= y 일때,
1) 대각선 이동을 하지 않는 방법 : (x*y)*w
2) x만큼 대각선 이동 후 나머지를 직선이동 : (x*s)+(y-x)*w
3) y만큼 대각선 이동 후 나머지를 작선이동 : (y*s)+(y-x)*w
4) 임의의 값 a만큼 대각선 이동, (a,a)에서 우상단으로 이동해서 x,y에 도달
  => (a,a)에서 우상단으로 a-x만큼 이동한다면 (x,y)에 도달할 수 있다.
     (a-(a-x),a+(a-x)) == (x,y)
     2a-x=y 에서 a = (x+y)/2 임을 알 수 있다. (x+y가 짝수일때)
  대각선 이동 횟수는 처음에 a만큼 이동, 우상단으로 (a-x)만큼 이동, 즉 2a-x번이다.
  a = (x+y)/2 이니 2a-x = y 이다.
  따라서 x+y가 짝수인 경우 : y번 대각선 이동으로 (x,y)에 도달할 수 있음을 알 수 있다.
  (x+y가 홀수인 경우에는 4번의 방식으로 (x,y-1)에 도착 후 오른쪽으로 1칸 이동하면 (x,y)에 도착할 수 있다.)
  비용 : y*s (x+y가 짝수), ((y-1)*s)+w (x+y가 홀수일 때)           

식으로 표현하고 나서 보니까 3)은 항상 2)보다 값이 크기 때문에 계산할 필요가 없다는 것을 알게 되었다.
1), 2), 4) 중 최소 비용을 return하면 답을 구할 수 있다.

x, y, w, s = map(int, input().split())

if x > y:
    x, y = y, x
# x < y
loadOnly = (x+y) * w
crossX = (x * s) + (y-x)*w
cross = (y*s) if (x+y) % 2 == 0 else ((y-1)*s) + w

print(min(loadOnly, crossX, cross))