백준 - 수리공 항승(Swift)

백준 - 수리공 항승(Swift)

 

 

 문제 설명

 

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

1449번: 수리공 항승

 

 나의 풀이

 

개인적으로 이해하기 힘들었던 문제이다.

양쪽 0.5라는 조건 때문인거같은데 해석을 하면 이렇다.

3 5 7 9의 파이프가 고장이 났을때 테이프의 길이가 3이라면 맨 앞의 3부터 5까지 묶을 수 있다. 

 

디테일하게 살펴보자면 2.5 | 3 | 3.5 | 4 | 4.5 | 5 | 5.5 에서 2.5~3.5에 한개 3.5~4.5에 한개 4.5~5.5에 한개해서 3의 길이로 3에서 5까지 커버가 가능한 것이다. 즉 테이프의 길이-1만큼을 커버할 수 있게 된다. 이게 문제의 해석이다.

 

아래 풀이는 다음과 같다.

3 5 9 10의 파이프가 고장났을때 테이플의 길이가 4라면 3에서 6까지는 커버가 가능하다. (위에서 언급) 즉 커버가 불가능한 숫자가 왔을떄 카운트를 증가시키면 된다. 여기서 커버는 새로 시작하는 점에서 다시 리셋해줘야한다. 

 

import Foundation

let nl = readLine()!.components(separatedBy:" ").map{Int($0)!}
let n = nl[0], l = nl[1]
var pipes = readLine()!.components(separatedBy:" ").map{Int($0)!}
var cnt = 0
pipes.sort(by: <)
var cover = 0
for pipe in pipes {
    if pipe > cover {
        cnt += 1
        cover = pipe + l - 1
    }
}
print(cnt)

 

 

 

 피드백

 

처음에는 문제를 보고 앞과 뒤의 원소차이가 1만 나면 묶어주는 건가 싶었는데 아니였다.(왜 이렇게 이해했을까 싶은,,)

그리디 문제를 풀다보면 생각보다 완전탐색 비슷한 부류의 문제가 많은 것 같다. 위 같은 경우 pipe전체에 대해 cover와 비교해준다.