[백준/Python] 1459. 걷기 (그리디) 🥈3️⃣

---

문제

좌표 (0,0)에서 (x,y)까지 이동할 때,
직선 이동(상하좌우)과 대각선 이동을 사용할 수 있다.

• 직선 이동 비용: w
• 대각선 이동 비용: s

최소 비용으로 목적지까지 이동하는 시간을 구하는 문제이다.

---

💻 정석 코드

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

case1 = (x + y) * w
case2 = min(x, y) * s + abs(x - y) * w

if (x + y) % 2 == 0:
    case3 = max(x, y) * s
else:
    case3 = (max(x, y) - 1) * s + w

print(min(case1, case2, case3))

---

코드 풀이

(0, 0)에서 (x, y)로 평행선과 대각선을 사용하여 이동할 때 걸리는 시간 3가지 경우로 나눌 수 있다.

1) 전부 직선 이동
2) 대각선 최대한 + 남은거리는 직선으로만
3) 가능한 한 대각선만 사용

이 세 가지 경우중에 최소값이 곧 결과가 된다.

1) 전부 직선 이동

(x + y) * w

2) 대각선 최대한 + 남은거리는 직선으로만

min(x, y) * s + abs(x - y) * w

3) 가능한 한 대각선만 사용

평행한 일직선의 거리도 대각선이동으로 가능하다.

예를 들어 (0,0)에서 (2,0) 로 이동하는 경우, x축으로 두 번 평행이동하는 방법도 있겠지만,
(0,0) - (1,1) - (2,0) 이렇게 대각선으로 두 번 이동하는 것도 가능하다.

단, 거리가 2의 배수인 경우는 위의 예시처럼 모두 대각선이동으로 가능하지만,
예를들어 (0,0)에서 (1,0)으로 이동하는 경우처럼 거리가 홀수인 경우는 대각선이동과 한번의 직선이동이 필요하다. (0,0) - (1,1) - (1,0)

if (x + y) % 2 == 0:
    max(x, y) * s
else:
    (max(x, y) - 1) * s + w

---

🔥 나의 시행착오

위의 풀이가 정석풀이라면, 지금부터는 그 전까지 내가 시행착오했던 풀이들이다.

첫 번째 시도 : 실패

처음에는 다음과 같은 아이디어로 접근했다.

• 가로1 + 세로1 이동은 대각선이동 하나로 대체가능하다.
• s < 2w : 대각선 이동이 유리함
• s > 2w : 평행이동이 유리함.

s < 2w이면 대각선이 유리하므로 최대한 대각선으로 이동하고,
나머지는 직선으로 이동한다.

이를 코드로 구현하면 다음과 같다.

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

max_s = min(x, y)
s_cnt = 0

if s < 2 * w:
    s_cnt = min(x, y)

print(((x - s_cnt) + (y - s_cnt)) * w + s*s_cnt)

1) 틀린 이유

이 코드는 남은 거리를 무조건 직선으로 처리한다고 가정했다.
하지만 실제로는 남은 거리도 대각선으로 처리하는 것이 더 빠를 수 있다.

2) 반례

x = 2, y = 0
w = 12, s = 10

• 내 코드 결과: 24
• 실제 정답: 20

이유:

• (0,0) → (1,1) → (2,0)
• 대각선 2번으로 이동 가능

즉, 한 축만 남았다고 해서 직선만 써야 하는 것은 아니다.

💻 나의 풀이 (개선 코드)

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

if s >= 2 * w:
    answer = (x + y) * w
else:
    diag = min(x, y) #대각선(diagonal)으로 이동하는 횟수
    diff = abs(x - y) #대각선으로 최대한 이동하고 남은 거리

    answer = diag * s

    if diff % 2 == 0:
        answer += min(diff * w, diff * s)
    else:
        answer += min(diff * w, (diff - 1) * s + w)

print(answer)

1) 핵심 로직

• min(x,y) 만큼은 대각선 이동
• 남은 거리 diff = abs(x-y) 처리

2) 남은 거리 처리

1. 짝수
   → 대각선만으로 정확히 도달 가능
   diff * s

2. 홀수
   → 마지막 1칸은 직선 필요
   (diff - 1) * s + w

3) 직선 vs 대각선 비교

min(diff * w, 대각선 방식)

지금 이 풀이에서는 s >= 2 * w에 따라 조건을 나눴지만,
이렇게 할 필요없이 정석코드에서처럼 case1, 2, 3을 구하고 이 중에 최소값을 결과로 출력하는 편이 훨씬 보기에도 편하고 간단하다.

---