백준 1459 걷기 / python

문제 : 1459

풀이 point

이 문제는 어떤 특별한 알고리즘을 필요로 하는 것이 아닌, 경우의 수를 나누어 분기를 설정하고 최선의 방법을 선택해야한다.

세준이는 가로, 세로, 대각선 셋중 하나의 방식을 선택해서 갈 수 있다. 이때 대각선은 세로와 가로 1칸씩 모두 이동할 수 있음을 알 수 있다.

경우의 수는 총 4가지이다.

풀이 방법

1. 2xW <= S일 경우
   이 경우는 가로 세로로만 가면 최소가 나오기 때문에 목적지로 까지의 거리xW를 하면 된다.
2. 2xW > S일 경우
   이 경우는 다시 세 가지로 나뉜다. ex) 목적지가 4, 6일 경우
   min(4,6) -> 4칸까지는 대각선으로 갈 수 있다. 다만 나머지 2칸은 대각선으로 갈지 가로 혹은 세로로 갈지는 경우의 수를 따져야 한다. 다음 경우의 수들은 나머지 2칸을 어떻게 할지에 대한 것이다.
   2-1. 나머지 칸(2)이 짝수라면 대각선으로 갈 수 있다.(↗↘)
   2-2. 나머지 칸이 홀수라면 대각선으로는 갈 수 없다. 짝수칸 까지만 대각선으로 가고 남은 칸은 가로 혹은 세로로 갈 수 있다.
   2-3. 대각선으로 가지 않고 나머지칸을 모두 가로 혹은 세로로 간다.

이 경우의 수를 모두 따져서 비용이 최소로 되는 값을 선택하면 된다.

풀이 코드

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

INF = 10**30

if W*2 <= S:
  print((X+Y)*W)
else:
  answer = 0
  m = min(X, Y)
  answer += m*S #ex) 4, 0까지
  d = (X-m)+(Y-m) #abs(X-Y)

  case1, case2, case3 = INF, INF, INF
  if d % 2 == 0: #대각선 처리가 가능
    case1 = answer + d*S
  else:
    case2 = answer + (d-1)*S + W

  case3 = answer + d*W

  print(min(case1, case2, case3))