[백준/Python] 1459 걷기(그리디)

BOJ

그리디 1459_걷기

문제로 이동!

문제

세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 (X, Y)에 위치한 집으로 가려고 한다. 세준이가 걸을 수 있는 방법은 두가지 인데, 하나는 도로를 따라서 가로나 세로로 한 블록 움직여서 이번 사거리에서 저 사거리로 움직이는 방법이고, 블록을 대각선으로 가로지르는 방법이 있다.

세준이가 집으로 가는데 걸리는 최소시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 위치 X Y와 걸어서 한 블록 가는데 걸리는 시간 W와 대각선으로 한 블록을 가로지르는 시간 S가 주어진다. X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고, W와 S는 10,000보다 작거나 같은 자연수이다.

예제 입력

입력: 4 2 3 10, 출력: 18
입력: 2 0 12 10, 출력: 20
입력: 135 122 43 28, 출력: 3929

풀이

해당 문제는 다양한 조건을 나누어 해결해야하는 문제이다. W와 S의 관계를 잘 관찰한 뒤 총 세가지 조건으로 나누어 문제를 해결하였다. 첫번째 조건은 S가 W보다 작을 때, 이 때는 가로 및 세로로 가는 것보다 대각선으로 가는게 훨씬 빠르다. 하지만 이 조건에서 한번 더 조건 분기 하는데, 남은 블록 수가 홀수라면 마지막 움직임은 가로 혹은 세로로 움직여야 최소 시간에 도착할 수 있다. 두번째 조건은 S가 2*W보다 작을 때, 세번째 조건은 나머지 조건을 제외한 경우이다.

solution

1. s 가 w 보다 작을때, s가 w2 보다 클 때 그리고 s가 w2 보다 작을 때로 조건을 나눈다.
2. s가 w*2 이하라면, x와 y중 최소값 만큼은 s로 움직인다. x와 y 차이값 만큼은 w로 움직인다.
3. s가 w보다 작다면, x와 y중 최소값 만큼은 s로 움직이고, x와 y의 차이값이 짝수라면 w만큼, 홀수라면 차이값-1 으로 s를 움직이고 마지막 w를 더해준다.

코드

    def solution(x,y,w,s):
        if s <= w:
            min_val = min(x, y)
            if abs(x-y) % 2 == 0:
                result = ((min_val) * s) + (abs(x-y) * s)
            else:
                result = ((min_val) * s) + ((abs(x-y)-1) * s) + w
        elif s > w*2:
            result = (x+y) * w
        else:
            min_val = min(x,y)
            result = ((min_val) * s) + (abs(x-y) * w)
    
        return result
    
    
    if __name__ == "__main__":
        x, y, w, s = map(int, input().split())
        print(solution(x,y,w,s))