[스위프트][백준 11509][💛골드 5] (그리디 알고리즘)

🧞‍♂️ 난이도

💛 골드 5

🧞‍♂️ 문제

백준 11509

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

🧞‍♂️ 유형

그리디 알고리즘

🧞‍♂️ 내 풀이

이 문제는 입력값이 커서 최소 선형시간으로 풀어야겠다는 생각은 했었는데 방법 생각하기 너무 어려웠다

방법은 화살이 날아가는 높이를 계속 기록하는거다. 예를 들어 풍선의 높이가 다음과 같으면

4 6 3 6 2

화살이 날아가면서 바뀌는 높이를 기록하는거다.

[0, 0, 0, 0, 0, 0, 0]

그래서 풍선을 하나씩 처리하면 4:

• 화살 하나 쏘고 터뜨린다
• 높이 3에 풍선 하나 추가해준다. [0, 0, 0, 1, 0, 0, 0] 6:
• 높이 6에 풍선있는지 확인해보고(없으니까) 화살 하나 더 쏜다
• 높이 5에 풍선 하나 추가해준다. [0, 0, 0, 1, 0, 1, 0] 3:
• 높이 3에 풍선있는지 확인해보고(있으니까) 터뜨린다
• 높이 2에 풍선 하나 추가해준다. [0, 0, 1, 0, 0, 1, 0] 6:
• 높이 6에 풍선있는지 확인해보고(없으니까) 화살 하나 더 쏜다
• 높이 5에 풍선 하나 추가해준다. [0, 0, 1, 0, 0, 1, 1] 2:
• 높이 2에 풍선있는지 확인해보고(있으니까) 터뜨린다
• 높이 1에 풍선 하나 추가해준다. [0, 1, 0, 0, 0, 1, 1]

이러면 총 화살 3개로 다 터뜨린걸 확인할 수 있다.

🧞‍♂️ 스위프트 풀이

let N = Int(readLine()!)!
let array = readLine()!.split(separator: " ").compactMap { Int($0) }

var arrowPosition = Array(repeating: 0, count: 1000001)
var answer = 0

for height in array {
    if arrowPosition[height] == 0 {
        answer += 1
    } else {
        arrowPosition[height] -= 1
    }
    arrowPosition[height - 1] += 1
}

print(answer)

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기