[백준][파이썬] 1459번 : 걷기(코드, 해설, 풀이)

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

1459번: 걷기

---

- 문제

 

  세준이는 (0,0)에서 출발을 해서 입력 X Y W S 중에서 (X,Y)까지 가야하는데, 한 블럭을 가는데는 W시간이, 대각선으로 가로질러 가는데는 S 시간이 걸릴 때 가장 빠르게 도착할 수 있는 시간을 고르는 문제이다. 이 문제를 해결하는 데 있어 다음과 같은 경우를 고려해야할 것 같다.

 

1. 블록을 한 번 이동하는 것이 대각선으로 가는 것보다 느린 경우

2. 블록을 한 번 이동하는 것이 대각선으로 가는 것보다 빠른 경우

 

 

---

- 해설

 

  위에서 나온 두 가지 경우를 가지고 문제를 해결해보자. 이제부터 블록을 한 번 이동 하는 데 걸리는 시간을 W, 대각선으로 이동하는데 걸리는 시간을 S라고 하겠다.

 

1. W > S

: W로 이동하는게 S로 이동하는 것보다 시간이 더 걸린다면 최대한 S로 이동하는 것이 좋다. 이때 두가지 상황으로 나뉠 수 있다.

    1) X == Y 이어서 대각선으로만 이동해도 집에 도착할 수 있다.

        - 모든 경우에 S로 이동하면 된다.

    2) X != Y 이어서 대각선으로만 이동하지 말고 한 블록씩 이동하는 부분도 있어야 한다. 

        - 최대한 S로 이동하되 X 혹은 Y 둘 중 하나에 먼저 도착하면 남은 만큼 W로 이동한다.

2. W <= S

: S보다 W로 가는 게 더 시간이 많이 걸린다면 모든 경우에 W로 이동하면 된다.

---

- 풀이

import sys
X, Y, W, S = map(int, sys.stdin.readline().split())
answer = 0
if 2*W <= S:
    print((X+Y)*W)
else:
    smaller = min(X, Y)
    answer = smaller*S
    absXY = abs(X-Y)
    if W > S:
        if absXY % 2 == 0:
            answer += absXY * S
        else:
            answer += (absXY-1)*S + W
    else:
        answer += absXY*W
    print(answer)

  S로 가는게 W로 가는 것 보다 더 좋은 상황일 때 X나 Y중에서 더 작은 값을 찾기 위해 smaller를 만들었다. 여기서 absXY % 2 ==0 조건문을 단 이유는 만약 우측으로만 두 칸을 가야할 때 S를 두번 사용하면 위로 대각선 한칸, 아래 대각선 한칸해서 우측으로만 두 칸을 이동할 수 있기 때문이다. 한 칸만 가면 되서 이런 방법을 사용하지 못한다면 어쩔 수 없이 W를 한 번 따로 더해주어야 한다.