만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 2836 수상 택시

23 Jun 2021

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

상근이가 0번에서 M번으로 이동할 때 다른 사람들의 탑승위치와 내리는 위치가 주어지면 0번에서 출발하여 다른 사람들을 태운 뒤 원하는 곳에 모두 내려주고 M번으로 최종적으로 이동하는 거리의 최솟값을 구하는 문제이다.

얼핏보면 이전에 풀었던 2170 선긋기 문제와 유사하다는 것을 짐작할 수 있을 것이다. 잘 생각해보면 상근이가 0번에서 M번으로 이동해야하기때문에 시작점 < 끝점 인 승객들은 별다른 노력 없이 가는길에 태워서 내려다주면 된다. 그렇다면 우리가 고려해야할 것은 시작점 > 끝점 인 승객들이다. 해당 승객들에 대해서만 선긋기를 한다고 생각하자.

2836wrong

다음과 같이 2명의 역으로 올라가는 승객이 있다고 하자. 우리가 해당승객을 만날때마다 거꾸로 갔다가 다시 오면 총 이동거리는 밑쪽의 선분들의 합과 같다.

2836right

하지만 서로 겹치는 승객들에 대해서 매번 거슬러 오를 필요없이 한번에 처리를 하게되면 위의 사진과 같은 이동을 하게된다. 이 때 묶어서 처리하면 겹치는 부분*2의 길이만큼 더 적게 이동한다는 것을 확인할 수 있다.

for _ in 0..<n {
    let xy = readLine()!.split(separator: " ").map{Int(String($0))!}
    let x = xy[0], y = xy[1]
    if x > y {
        line.append((y, x))
    }
}
line.sort(by: {$0.0 < $1.0})

따라서 입력을 받았을 때 x > y인 경우만 우리가 고려할 line에 넣어주고 line을 sort해서 2170과 같은 방법으로 총 선분의 길이를 구해준다. 결과에 2를 곱해주고 m과 더해주면 끝! 이 때 m이 최대 109 이므로 Int64로 표현해줘야 안전하다는 것 기억하자.

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
var line:[(Int, Int)] = []
for _ in 0..<n {
    let xy = readLine()!.split(separator: " ").map{Int(String($0))!}
    let x = xy[0], y = xy[1]
    if x > y {
        line.append((y, x))
    }
}

line.sort(by: {$0.0 < $1.0})
var r = -1, l = -1
var result:CLongLong = 0
for m in line {
    if r < m.0 {
        l = m.0
        r = m.1
        result += CLongLong(r-l)
    }
    else if r < m.1 {
        result += CLongLong(m.1-r)
        r = m.1
    }
}
result *= 2
result += CLongLong(m)
print(result)

Related posts