[Python/파이썬] 백준 1459번 걷기

1459번: 걷기

 

코드

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

# 평행 이동만
case1 = (x+y)*w
# 최대한 대각선 이동
if (x+y) % 2 == 0:  # 대각선 이동만 해도 됨
    case2 = max(x, y)*s
else:   # 1번은 평행 이동 필요
    case2 = (max(x, y)-1)*s+w
# 평행 + 대각선
case3 = min(x, y)*s + abs(x-y)*w

print(min(case1, case2, case3))

 

처음에는 왼쪽 위가 (0, 0), 오른쪽 위가 (x, y)인 직사각형 범위를 벗어나지 않는다고 생각하여 BFS로 풀려고 했는데 생각해보니 대각선 이동까지 합치면 무조건 그 범위 내에서 움직이는 것이 최소가 아닐 수도 있다.
이건 문제에 주어진 예제 3으로 생각하면 편하다. 처음에 생각한대로 하면 세준이는 직선 이동만 할 수 있는데, 정답은 대각선 이동을 2번 한 값인 20이다. (x, y) 범위를 벗어날 수도 있다는 것을 고려하면 이동할 수 있는 범위를 더 넓게 잡아야하는데 자칫 잘못하면 연산이 너무 많아진다. 그래서 다른 방법을 생각했다.

 

생각해보면 세준이가 (0, 0)에서 (x, y)로 평행과 대각선을 사용하여 이동할 때, 나오는 최소 시간의 가짓수는 3가지 뿐이다.

 

1. 평행 이동만 하기

2. 최대한 대각선 이동을 하기

3. 평행 이동과 대각선 이동을 적절히 섞기

 

1은 그냥 세로로 x만큼 가고, 가로로 y만큼 가면 되므로 x+y에 w를 곱해주면 된다.

2는 2가지 경우로 나누어봐야 한다. 만약 x+y 값이 2의 배수라면 대각선 이동만으로도 목적지에 도착할 수 있다. 그렇지만 x+y가 2의 배수가 아니라면 대각선 이동만으로는 절대 목적지에 도착할 수 없으므로 어쩔 수 없이 한 번의 평행 이동은 필요하다. 그렇기 때문에 x, y 중 큰 값보다 한 번 모자라게 대각선 이동을 하고 한 번은 평행 이동으로 채운다.

3은 대각선과 평행 이동을 적절히 섞는것이다. x, y 둘 중 작은 값에 닿을 때까지 대각선 이동을 하고 그 이후는 평행 이동을 하는 식이라고 생각하면 된다.

 

이렇게 구한 3가지 경우의 수 중 가장 최소값을 구하면 문제의 답이다.