[백준 1459번] 걷기 (Python)

백준 1459번과 자료구조 과목 학습 후 정리한 포스팅 입니다.

이번 포스팅에서는 백준 1459번에 대해 학습합니다.

https://www.acmicpc.net/problem/1459

1459번: 걷기

 

I) 문제

 

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

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

II) 입력

 

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

 

III) 출력

 

첫째 줄에 세준이가 집에가는데 걸리는 최소시간을 출력한다.

 

IV) 트러블 슈팅

가능한 경우를 최대한 찾아보려고 했다.

핵심은  x, y의 차가 2의 배수이거나 배수이지 않거나 2가지이다!

 

i) x, y의 차가 2의 배수인 경우 한 블록씩만 가거나 대각선으로만 가거나 한 블록과 대각선의 조합으로 집에 도착할 수 있다

ex) (4, 2)에 집이 위치하는 경우 

       1. 한 블록씩만 간다 ( ㅡ, ㅡ, ㅡ, ㅡ, |, |) 

       2. 대각선으로만 간다 ( /, /, /, \)

       3. 한 블록씩 2칸 가고 대각선으로 2칸 간다. (ㅡ, ㅡ, /, /)

3번을 구현하는 방법은 대각선으로 한번 이동하면 x, y 각각 한 블록씩 이동하는 것과 같다.

따라서 x, y중 작은 수 만큼은 한 블록씩 이동하고 x, y의 차이만큼은 대각선으로 이동한다.

import sys
input = sys.stdin.readline

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

# 1. x-y가 짝수일 경우
if abs(x - y)%2==0:
    # i) 한 블록씩만 가기 
    time_1 = (x + y) * w
    
    # ii) 대각선으로만 가기
    time_2 = max(x, y) * s
    
    # iii) 한 블록 + 대각선으로 가기
    time_3 = (min(x, y) * s) + (abs(x-y) * w)
else:
	break
# 최소 경로 출력
print(min(time_1, time_2, time_3))

 

ii) x, y의 차가 2의 배수가 아닌 경우 한 블록씩만 가거나 한 블록과 대각선의 조합으로 집에 도착할 수 있다

ex) (5, 2)에 집이 위치하는 경우 

       1. 한 블록씩만 간다 (ㅡ, ㅡ, ㅡ, ㅡ, ㅡ, |, |) 

       2. 대각선으로 최대한 간다 ( /, /, \, \, ㅡ)

       3. 한 블록씩 최대한 간다. (ㅡ, ㅡ, ㅡ, /, \)

2번을 구현하는 방법은 x, y 중 최댓값에서 1을 뺀 값 만큼 대각선으로 이동하고 한 블록 이동하면된다.

3번을 구현하는 방법은 대각선으로 한번 이동하면 x, y 각각 한 블록씩 이동하는 것과 같다. 

따라서 x, y중 작은 수 만큼은 한 블록씩 이동하고 x, y의 차이만큼은 대각선으로 이동한다.

import sys
input = sys.stdin.readline

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

# 2. x-y가 홀수일 경우
if abs(x - y)%2 !=0:
    # i) 한 블록씩만 가기 
    time_1 = (x + y) * w
    
    # ii) 대각선으로 최대한 가고 한 블록씩 가기
    time_2 = (max(x, y) - 1) * s + w
    
    # iii) 한 블록 + 대각선으로 가기
    time_3 = (min(x, y) * s) + (abs(x-y) * w)
else:
	break
# 최소 경로 출력
print(min(time_1, time_2, time_3))

 

 

 

 

V) 코드

위의 두 경우 코드를 간단화하면 다음과 같다

import sys
input = sys.stdin.readline

x, y, w, s = map(int, input().split())
# 할 수 있는거 다 해보고 최소값 출력해주기
# i) 한 블록씩만 가기 
time_1 = (x + y) * w
# 1. x-y가 짝수일 경우
if abs(x - y)%2==0:
    # ii) 대각선으로만 가기
    time_2 = max(x, y) * s
# 2. x-y가 홀수일 경우
else : 
    # ii) 대각선으로 최대한 가고 한 블록씩 가기
    time_2 = (max(x, y) - 1) * s + w

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

print(min(time_1, time_2, time_3))

 

 

 

 

<Summary>

 

-  코드 짜기 전에 경우부터 나누기!

 

 

 

*유의사항

- 알고리즘 공부 중인 인공지능공학과 학부생이 공부하여 남긴 정리입니다.

- 정확하지 않거나, 틀린 점이 있다면 댓글로 알려주시면 감사하겠습니다.