백준 1459 - 걷기 - swift

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

1459번: 걷기

 

 

 

 

브론즈1이지만 생각보다 고민을 요한다. 

그렇기때문에 정답률이 20%임을 보여주는 것 같다. 

 

우선 문제의 X,Y의 범위가 최대 10억이므로, 이를 효율적으로풀지않는다면 위험하다.

 

그래서 효율적으로 푸는 ( 그리디 ) 방법이 필요한데, 

기본적인 수학지식을 필요로한다. 

두 점사이의 거리를 구하는 방정식을 요구하는것도 아니다. 

 

문제의 해법은 특정점을 가기위해 최소비용이 얼마인지를 깨닫는 것이다. 

 

시작지점은 (0,0) 이므로,  예를들어  (1,1) 지점을 가기위한 최소비용은 얼마일까? 

대각선(S)은 한번만 가면되고, 가로,세로이동방법(W)은 2번필요하다.

이것만 깨닫는다면 조금만 더 고민하면 풀수있다. 

 

그러므로, 여기서 알 수 있는 사실은,  특정점을 가기위해서  W*2 와 S를 비교하면 된다. 

S가 더작다면 무조건 대각선으로 특정점까지 가는것이 최소비용일것이다. 

 

그렇다면 도착지점까지 가기전에, 대각선으로 최대한 빠르게 이동하는것이 가장효율적일것이다. 

그러므로 최대한 대각선으로갈수있는 곳 까지 이동해야한다. 

이점은 도착지점의 최소값을 통해서 알 수 있다. 

도착지점이 (4,2) 라면,  (2,2)까지는 대각선으로 이동하는것이 가장 효율적이다. 

(2,2)에서부터는 직선으로 두번만 가면된다. 

 

과연 직선으로 두번가는것이 가장 최소비용일까? 

예를들어, (0,0)에서 (0, 2) 로 간다면, 

최소비용이 될경우는 2가지가있다. 

하나는 직선으로 두번가는경우와 ,

 ^로 대각선을 두번가는경우이다. 

 

즉 2*W 과 2*S중에서 더 작은 비용을 선택하는 것이다. 

즉, 직선으로가는 거리에서 2로 나눈몫까지 비용을곱해준다.

 

2로나누어떨어지지않는경우는 직선으로가면될까? 

한거리만 남은경우에서는 직선으로 최소한번 가지않고서는 대각선으로만 돌아서 갈수가없다. 

그러므로 나머지는 직선으로 비용을 더해준다. 

 

let q = readLine()!.split(separator: " " ).map{Int(String($0))!}

let minV = min(q[0], q[1]), left = max(q[0], q[1])-minV, W = q[2], S = q[3]

var ans = 0

ans += S <= W*2 ? minV*S : minV*2*W
ans += 2*S <= W*2 ? left/2*2*S : left/2*2*W
ans += left%2*W

print(ans)