[백준] (실패) 1459 걷기

풀이

나는 처음에 이동이 우측,상단 또는 우측 상단으로 대각선 이렇게 인 줄 알았는데, 이게 아니더라,,

처음에는 아래와 같이 풀었다.'

import sys
from collections import deque
input = sys.stdin.readline

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

# 대각선보다 하단+우측 비용이 더 적은 경우 -> 아예 하단/우측 방향으로만 이동 
if 2*W < S:
    print((X+Y)*W)
# 대각선이 더 빠른 경우 -> 대각선으로 이동할 수 있는 위치까지 이동 + 하단/우측 이동
else:
    print(min(X,Y)*S + (max(X,Y)-min(X,Y))*W)

그러나 예제 3을 보면 2 0 12 10 일때 20이 나온 모습을 확인할 수 있다. 이 말은 즉슨, 대각선 방향이 우측 상단 뿐만 아니라, 좌측 하단도 가능하다는 뜻..

그러면 W > S 라면 이동 거리에 S 를 곱하는게 최소이다. 그러나 이동 거리가 홀수인 경우에는 대각선만으로 이동하는 경우 목적지에 도달하지 못한다. 1번은 우측 또는 상단으로 이동해줘야 한다.

그러면 조건 분기는 다음과 같다

2*W < S 인 경우 (우측/상단으로만 이동)
-> (X + Y) 곱하기 S

S < W 인 경우 (최대한 대각선만으로 이동)
1. X+Y 가 짝수인 경우 -> MAX(X,Y) 곱하기 S
2. X+Y 가 홀수인 경우 -> (MAX(X,Y)-1) 곱하기 S + W

위 두 경우가 아닌 경우 (대각선 +우측/상단 적절히)
-> min(X,Y) 곱하기 S + abs(X-Y) 곱하기 W

*대각선의 경우 MAX 를 사용해서 대각선 이동 개수를 구하는데, 이해가 잘 되지 않는다면 예제를 통해 수식을 예측해보는것도 좋을 것 같다.

정답 코드

import sys
input = sys.stdin.readline

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

if 2*W < S:
    print((X+Y)*W)
elif S < W:
    if (X+Y)%2 == 0:
        print(max(X,Y)*S)
    else:
        print((max(X,Y)-1)*S + W)
else:
    print(min(X,Y)*S + abs(X-Y)*W)