백준 13904 과제

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

분류: 그리디

---

접근방식

그리디하게 점수가 높은 과제부터 배정해주는 방식으로 해결했습니다.

점수가 높은 과제를 마감일에 처리해주되 해당 날이 이미 배정되어 있다면 비어 있는 날을 찾아 그 전날에 배정해주는 방식으로 해결했습니다.

만약

1 30
2 40
2 50

주어졌다면, 점수가 가장 높은 2 50을 먼저 배정해주고
그 다음 높은 2 40을 배정해주려 하는데, 2일차는 이미 차서 그 전날인 1일차에 배정해주는 방식입니다.

이미 점수가 높은 순서대로 배정시키기 때문에 다 차있어서 배정할 수 없다면 그게 최선일거라고 판단했습니다.

 

해결방법

protocol Readable {
    func readSingleValue() -> String
    func readArray(with separator: Character) -> [String]
}

extension Readable {
    func readSingleValue() -> String {
        return readLine()!
    }
    
    func readSingleValue() -> Int {
        return Int(readLine()!)!
    }
    
    func readArray(with separator: Character) -> [String] {
        return readLine()!.split(separator: " ").map { String($0) }
    }
    
    func readArray(with separator: Character) -> [Int] {
        return readLine()!.split(separator: " ").map { Int(String($0))! }
    }
}

class BOJ13904: Readable {
    
    func input() {
        n = readSingleValue()
        for _ in 0..<n {
            let data: [Int] = readArray(with: " ")
            works.append((data[0], data[1]))
        }
    }
    
    // MARK: Properties
    
    var n: Int!
    var works = [(dueDate: Int, score: Int)]()
    
    // MARK: Solution
    
    func solution() {
        input()
        works.sort(by: { $0.score > $1.score })
        var timeTable = [Bool](repeating: false, count: 1001)
        var score = 0
        
        for work in works {
            var dueDate = work.dueDate
            while timeTable[dueDate], dueDate > 0 {
                dueDate -= 1
            }
            
            if dueDate != 0 {
                timeTable[dueDate] = true
                score += work.score
            }
        }
        print(score)
    }
}

BOJ13904().solution()

 

 

배운점