BOJ 백준 1449 수리공 항승

출처: www.acmicpc.net/problem/1449

분류: 그리디

---

접근방식

테이프의 좌 우로 0.5를 남겨둬야 한다고 했으니 테이프 길이 - 1 만큼의 구멍은 한 번에 막을 수 있습니다.

구멍을 막을 때마다 테이프의 길이는 줄어들겠죠. 테이프의 길이보다 구멍까지의 간격이 더 크다면 테이프를 새로 끊어야 합니다.

현재 남은 테이프로 남은 구멍을 메꿀 수 있는지 확인하고 아니면 테이프를 새로 끊어줍니다.

 

다른 분의 접근법을 보고 알았는데요.

더 쉽게 생각하면 현재 구멍의 위치 + 테이프길이-1 만큼까지 커버가 가능하다는 말이 됩니다.
테이프를 새로 끊을 때 현위치 + 테이프길이-1 까지를 커버 가능한 범위라고 생각하면, 다음 위치가 커버 가능한 범위를 벗어나면 테이프를 새로 끊어주면 됩니다.

 

해결방법

 

배운점

let n = readLine()!.split(separator: " ").map{Int($0)!}
var leaks = readLine()!.split(separator: " ").map{Int($0)!}
leaks.sort()

var used = 0
var current = 0
var tape = 0
for leak in leaks {
    if tape < leak - current {
        used += 1
        tape = n[1] - 1 // 테이프를 새로 끊음
    } else {
        tape -= leak - current
    }
    current = leak
}

print(used)

 

보다 간결한 다른 풀이

let n = readLine()!.split(separator: " ").map{Int($0)!}
var leaks = readLine()!.split(separator: " ").map{Int($0)!}
leaks.sort()

var cover = 0
var used = 0
for leak in leaks {
    if leak > cover {
        used += 1
        cover = leak + n[1]-1
    }
}

print(used)

 

회고

 

쉬운 문제였는데 생각보다 오래걸렸습니다 ;;; 

간단하게 생각할 수 있는데 어렵게 생각하는 경향이 있는 것 같네요. 

연습하면 점점 나아지겠죠!!!