백준 1459번 걷기 python

백준 1459 걷기 C++

문제 설명

문제

세준이는 집에서 학교까지 가장 빠르게 가는 시간을 구해야 합니다. 집은 (0,0)에, 학교는 (X,Y)에 위치해 있습니다. 세준이는 오른쪽, 위쪽, 오른쪽 위 대각선으로만 이동할 수 있습니다. 오른쪽, 위쪽으로 한 칸 이동하는 데 걸리는 시간은 W, 대각선으로 한 칸 이동하는 데 걸리는 시간은 S입니다.

---

테스트케이스

4 2 3 5

3 5 3 5

2 0 12 10

---

문제 작동 원리

예를 들어 X=2, Y=0, W=12, S=10이라면,

• 방법 1 — 직선만 사용
  오른쪽으로 2번 이동
  총 비용 = \(2 \times W = 2 \times 12 = \textbf{24}\)
• 방법 2 — 대각선만 사용
  (0,0) → (1,1) 대각선 이동 = S = 10
  (1,1) → (2,0) 대각선 이동 = S = 10
  총 비용 = \(10 + 10 = \textbf{20}\)

이 경우 대각선 이동이 더 저렴하므로 최적 경로는 방법 2이고, 최소 시간은 20입니다.

---

아이디어

1. 만약 \(2W < S\) 이면, 가로, 세로로만 이동하는 것이 최소 비용입니다.

조건

• 출발: (0,0)
• 도착: (4,2)
• W = 3, S = 10
• W < S → 직선만 이용하는 것이 최소 비용
• 표 크기: y=0~2, x=0~4 범위 (3행 5열)
• 이동 순서대로 값 기록

0단계 (출발점)

y\x	0	1	2	3	4
0	0
1
2

1단계 (1,0)

y\x	0	1	2	3	4
0	0	3
1
2

2단계 (2,0)

y\x	0	1	2	3	4
0	0	3	6
1
2

3단계 (3,0)

y\x	0	1	2	3	4
0	0	3	6	9
1
2

4단계 (4,0)

y\x	0	1	2	3	4
0	0	3	6	9	12
1
2

5단계 (4,1)

y\x	0	1	2	3	4
0	0	3	6	9	12
1					15
2

6단계 (4,2) 도착

y\x	0	1	2	3	4
0	0	3	6	9	12
1					15
2					18

요약하면

우리는 대각선을 사용하는 것보다 가로, 세로 방향을 쓰는 게 항상 최적이라면 가로, 세로만 써서 값을 구할 수 있습니다.

---

2. 가로, 세로 이동(W) < 대각선 이동(S) < 가로, 세로 2번(2W) 일 경우에는 대각선으로 가로, 세로만큼 최대 이동 후 남은 거리는 최소값으로 갑니다.

조건

• 시작: (0,0)
• 목표: (4,2)
• W=3, S=5
• 표 크기: y=0~2, x=0~4 (3행 5열)
• 한 칸씩 이동, 최적 경로만 채움

0단계 (출발점)

y\x	0	1	2	3	4
0	0
1
2

1단계 — (1,1) (대각)

y\x	0	1	2	3	4
0	0
1		5
2

2단계 — (2,2) (대각)

y\x	0	1	2	3	4
0	0
1		5
2			10

3단계 — (3,2) (직선 → W=3)

y\x	0	1	2	3	4
0	0
1		5
2			10	13

- 만약 대각선으로 간다면

y\x	0	1	2	3	4
0	0
1		5		15
2			10

4단계 — (4,2) (직선 → W=3)

y\x	0	1	2	3	4
0	0
1		5
2			10	13	16

- 만약 대각선으로 간다면

y\x	0	1	2	3	4
0	0
1		5		15
2			10	13	20

결과

• 최적 경로: (0,0) → (1,1) → (2,2) → (3,2) → (4,2)
• 총 비용: 16
• 규칙: 대각선 최대한 사용 후, 나머지는 직선

요약하면

대각선으로 최대한 이동한 후에, 대각선을 사용하는 것과 가로, 세로를 사용하는 것 중 더 싼 것을 골라야 합니다.

---

3. 가로, 세로를 두 번 이동하는 것보다 대각선이 싸다면 대각선을 이용합니다. 그러나 대각선으로 \(|X-Y|\)가 홀수인 곳은 이동할 수 없습니다.

홀수인 경우

---

1단계 — 0번째 이동

y\x	0	1	2
0	0
1

2단계 — 1번째 이동

• (0,0) → (1,1) (대각 이동) : 비용 = 10

y\x	0	1	2
0	0
1		10

3단계 — 2번째 이동

• (1,1) → (2,1) (직선 이동) : 비용 = 10 + 12 = 22

y\x	0	1	2
0	0
1		10	22

✅ 최소 비용 경로: (0,0) → (1,1) → (2,1)
✅ 총 비용: 22

---

짝수인 경우

네, X=2, Y=0, W=12, S=10에 대해서 아까 방식 그대로 최적 경로만 표로 만들겠습니다. 출발: (0,0) → 도착: (2,0)

---

1단계 — 0번째 이동

y\x	0	1	2
0	0
1

2단계 — 1번째 이동

• (0,0) → (1,1) (대각 이동) : 비용 = 10

y\x	0	1	2
0	0
1		10

3단계 — 2번째 이동

• (1,1) → (2,0) (대각 이동) : 비용 = 10 + 10 = 20

y\x	0	1	2
0	0		20
1		10

✅ 최소 비용 경로: (0,0) → (1,1) → (2,0)
✅ 총 비용: 20

---

전체코드

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

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

---

결론

• 직선 이동(W)과 대각선 이동(S)의 비용을 비교하여 최적의 이동 방법을 선택해야 합니다.
• 경우 1: \(2W \le S\)
  대각선 이동이 직선 2번 이동보다 비싸거나 같다면, 오직 직선 이동만 사용하여 \( (X+Y) \times W \)의 비용을 계산합니다.
• 경우 2: \(W > S\)
  대각선 이동이 직선 1번 이동보다 싸다면, 최대한 대각선으로 이동하는 것이 유리합니다.
  • 두 지점의 거리 차이 \(|X-Y|\)가 짝수이면, 직선 이동 없이 \( \max(X, Y) \times S \)의 비용으로 도착할 수 있습니다.
  • 두 지점의 거리 차이 \(|X-Y|\)가 홀수이면, 마지막 한 칸은 직선으로 이동해야 하므로 \( (\max(X, Y)-1) \times S + W \)의 비용이 듭니다.
• 경우 3: \(W \le S < 2W\)
  대각선 이동이 직선 2번 이동보다는 싸지만, 직선 1번 이동보다는 비싸거나 같다면, 대각선으로 이동할 수 있는 만큼 이동한 후 남은 거리를 직선으로 이동합니다. 이 경우 비용은 \( |X-Y| \times W + \min(X, Y) \times S \)로 계산합니다.
• 최종 답은 위 세 가지 경우 중에서 가장 최소 비용을 찾는 것입니다. 제시된 코드는 이를 세 가지 경우로 나누어 처리하고 있습니다.