백준 - 과제(Swift)

백준 - 과제(Swift)

 

 

 문제 설명

 

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

13904번: 과제

 

 나의 풀이

 

점수를 최대한으로 얻기 위해서 큰 점수부터 배치를 하는 게 가장 그리디한 접근이다. 

 

여기서 관건은 마감기한을 고려해서 큰 점수를 배치하는 것인데, 이는 방문표시를 통해 해결할 수 있다.

 

예를 들어보자. 

문제의 예시를 점수별로 정렬하면 아래처럼 된다.

4 60

2 50

4 40

3 30

1 20

4 10

6 5

 

(4 60)을 먼저 뽑았다면 마감기한이 4일을 가장 마지막에 배치를하는 것이기 떄문에 4일의 방문표시를 true로 둔다.

다음 (2 50)은 2일이 마감기한이므로 2일 중 제일마지막인 2일(1일에 배치할수도 2일에 배치할수도 있다.)에 넣는다.

(4 40)은 4일이 방문되어있기 때문에 남은 일수중 가장 마지막인 3일에 배치를 한다.

그리고 (1 20)과 (4 10)은 방문되어있기 때문에 패스가되고 (6 5)는 6일이 마감기한일이라면 6일째에 넣으면 되기 때문에 배치를 하고 끝내면 된다.

 

이렇게하면 점수가 가장 많은것들을 가장 마지막에 배치함으로써 최대값을 구할 수 있게 된다.

 

import Foundation

let n = Int(readLine()!)!
var arr = [(dueDate: Int, score: Int)]()
var visited = [Bool](repeating: false, count: 1001)
var sum = 0
for _ in 0..<n {
    let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
    arr.append((input[0], input[1]))
}

arr.sort(by: {$0.score > $1.score})

for x in arr {
    var dueDate = x.dueDate
    while visited[dueDate], dueDate > 0 { //마감기한이 이미 등록되었다면 1을 빼줘서 전날로
        dueDate -= 1
    } 
    
    if dueDate != 0 {
        visited[dueDate] = true
        sum += x.score
    }
}

print(sum)