[알고리즘/그리디] 1459번 : 걷기 - python

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

1459번: 걷기

 

---

• 문제
• 소요시간: 38분 21초

---

• 설계하기(접근방법) 

1. 입력받기

목표 좌표, 이동 가중치를 입력받는다

 

2. 구현하기

처음에 while문으로 돌려서 시간초과가 났다

 

사실 좌표값 만큼 빼는 것이기 때문에

굳이 while문을 안돌리고 몫만 구해서 빼도 되는 것이었다

 

먼저 x,y 중 하나가 0이 될때까지 만들고, 둘 다 짝수로 만든다 ->

그래서 평행선에서 대각선 이동으로 목적지에 도달할 수 있다

 

대각선 이동 은 평행 이동 2번과 같으니

1) 대각선 이동 이 평행 이동 2번보다 가중치가 크다면

평행 이동이 효율적이다

2 )아니라면 대각선 이동이 가능할 때까지 해야한다

 

1) 조건이라면 x,y 중 둘중에 작은 수만큼 둘다 빼준다

그러면 둘 중 하나는 0이 될것이고

0이 아닌 수는 짝수로 만들어준다 (평행이동 +1을 해주어야 한다)

 

그 후

대각선 이동이 평행 이동 1번보다 가중치가 크면

평행이동으로 마무리하면 되고 :(0이 아닌 수만큼 w를 곱해준다)

대각선 이동이 효율적이라면

대각선 이동으로 마무리한다 (0이 아닌 수만큼 s를 곱해준다)

 

 

3. 출력하기

 

 

---

• 코드(출력)

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

time = 0

# 대각선의 가중치가 낮다면 대각선 이동
if 2 * w >= s:
    sum = min(x,y)
    time += s * sum
    x -= sum
    y -= sum

# 홀수 제거 -> 다음 대각선 가중치 비교 때 대각선 이동을 가능하게 하기 위해서
if y % 2 != 0:
    y -= 1
    time += w
if x % 2 != 0:
    x -= 1
    time += w
 
# 대각선 혹은 평행 이동
if w > s:
    time += y * s + x * s
else:
    time += y * w + x * w



print(time)

 

---

• 얻어갈 부분

1. while문으로 돌릴 필요가 있는지 생각하고 코드를 짜자