백준 1449번 Swift 알고리즘 연습 - 수리공 항승_그리디

이번에도 그리디 문제다.

 

누수가 있는 곳을 찾아 놓고, 누수가 시작되는 지점에서부터 고민을 해주면 된다.

누수가 있는 곳부터 L만큼 위치를 이동시켜주고 다시 누수를 찾아주면 된다.

 

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 파이프의 길이가 1000 이하이기 때문에 leak 배열을 1001까지(0을 포함하여 index가 하나 늘어남) true로 만들어준다.
2. 이 중 insert2에 입력받는 누수 위치를 false로 지정해준다.
3. leak배열에서 count 위치를 계속해서 증가시켜가다가 false를 찾으면 그 위치부터 L만큼 인덱스를 옮겨준다.
4. 그렇게 위치를 조금씩 조정해가면서 필요한 테이프의 개수를 찾아준다.

 

 

* 1449번

let insert1 = readLine()!.split(separator: " ").map{Int($0)!}
let insert2 = readLine()!.split(separator: " ").map{Int($0)!}
var leak = Array(repeating: true, count: 1001)
var count = 0
var ans = 0

for i in insert2 {
    leak[i] = false
}

while count <= 1000 {
    if leak[count] == false {
        count += insert1[1]
        ans += 1
    } else {
        count += 1
    }
}

print(ans)

 

 

정리(Today I Learned)

1. 없음