[백준] 1459번 걷기

 

이제 그리디 문제를 풀어볼까 합니다.

 

접근법

- 최소시간을 구하는 문제

- 조건에 맞게 분기

- 공통 좌표값과 여분 좌표값

  ex) (x,y) = (2,5) → 공통 좌표값 : 2 , 여분 좌표값 : 3

- 비교1 : 대각선 이동 vs 한 블록 이동 *2 -> 공통 좌표값 이동 시 

- 비교2: 대각선이동 vs 한 블록 이동 → 공통 좌표값 외 여분 좌표 이동 시

 

조건 비교

비교1

   1) 공통 좌표값까지 대각선 이동 후 여분 좌표값 한 블록 이동

비교2

   2-1) 공통 좌표값까지 대각선 이동 후 여분 좌표값만큼 대각선 이동

   2-2) 공통 좌표값까지 대각선 이동 후 여분 좌표값-1만큼 대각선 이동 후 1만큼 한 블록 이동

 

3) 한 블록 이동만 사용

 

 

코드 : 조건문 활용

x,y,w,s = map(int,input().split())
cm_move = min(x,y)
indep_move = max(x,y) - cm_move
if 2*w > s :
    if w > s :
        if indep_move % 2 == 0:
            ans = max(x,y) * s
        else :
            ans = (cm_move * s) + ((indep_move-1)*s + w )
    else :
        ans = (cm_move * s) + (indep_move * w)
else :
    ans = (x+y)* w
    
print(ans)

 

코드 : 경우의 수

조건문을 재구성해서 경우의 수로 구분했습니다.

x,y,w,s = map(int,input().split())
cm_move = min(x,y)
indep_move = max(x,y) - cm_move

way1 = (x+y)* w
way2 = max(x,y) * s if indep_move % 2 == 0 else (cm_move * s) + ((indep_move-1)*s + w )
way3 = (cm_move * s) + (indep_move * w)

ans = min(way1, way2, way3)
print(ans)