[백준] (Swift) 1449번 - 수리공 항승 (feat. 그리디)

🟣 문제풀이

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

1449번: 수리공 항승

 

🟣 나의 문제 풀이

아니 처음에 문제 읽고 0.5씩 겹친다길래,, 뭔의민가 싶어서 아래처럼 색칠이 되는 줄 알았다. 그니까 수리구멍 한개가 1인줄;; 

근데 뭐 어쨌든 이게 아니었고,,, 그냥 테이프 길이가 L 로 고정이니까 그걸로 몇구멍을 막을 수 있냐는 거였다. 그냥 간단했다 아래처럼!!

이렇게 ... 문제를 해석하는데만 20분을 넘게 쓴듯 ㅋㅋㅋㅋㅋ (문해력이 문젠가,,)
어쨌든, 여기서 중요한 포인트가 있다. 테이프의 길이에 집중해보자.

내가 그린 두번째 연두색 그림을 살펴보자. 테이프는 3에서 두번재 테이프를 새로 써야한다. 테이프의 맨처음 시작점은 1이고, 1부분에 테이프를 붙여버리면, 2는 자동으로 막힌다. 3일때 새로운 테이프를 붙여야한다. 여기서 새로운 테이프를 사용하기 위한 조건은 아래와 같다.

(첫번째 지점 제외하고 두번재 누수지점부터 확인해보면,)
누수지점 - 내가 현재 검토하고있는 누수지점 < 테이프의 길이 
이 경우일때는, 한개의 테이프 (이전에 붙여놓은 테이프)로 자동으로 막힌다.
위 경우에서는 2 - 1 < 2 이기 때문에, 2번지점은 첫번째 테이프로 자동으로 막힌다!

만약, 누수지점 - 내가 현재 검토하고있는 누수지점 >= 테이프의 길이 라면,
새로운 테이프를 꺼내들어야한다!! 

첫번재 지점을 제외하고 두번째 누수지점부터 확인한 이유는, 첫번째 누수지점에는 무조건!! 테이프를 붙여야하기 때문이다. 이것은 분기처리로 처리해주자!

그리고 제일중요한건, 누수지점을 오름차순으로 sort해주어야한다. 뒤죽박죽 입력될 수 도 있기 때문에 오름차순으로 누수지점을 정렬해준 뒤, 앞뒤 누수지점들을 잘 파악할 수 있도록 해주어야한다.

🟣 정답코드

import Foundation

let nl = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nl[0]
let tapeLen = nl[1]
let arr = readLine()!.split(separator: " ").map{ Int($0)! }.sorted(by: <)

var start = 0
var tapeCnt = 0

for i in 0..<n {
    if i == 0 {
        tapeCnt += 1
        start = arr[i]
        continue
    }

    if arr[i] - start >= tapeLen {
        tapeCnt += 1
        start = arr[i]
    }
}

print(tapeCnt)