[백준 15486] 퇴사 2 (Swift)

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

 

DP 동적프로그래밍

그림의 표처럼 날짜 별로 할 수 있는 상담의 걸리는 일수와 얻을 수 있는 금액이 주어진다.

상담을 하고 있는 동안 다른 상담을 할 수는 없기 때문에 최대 이익을 얻기 위해 몇개만 골라서 상담해야한다.

얻을 수 있는 최대 수익을 출력하는 문제

 

접근방법

처음엔 dp 배열에 해당일에 상담을 하는 경우 얻을 수 있는 최대 이익, 상담을 하지 않는 경우 얻을 수 있는 최대 이익을 계산해서 저장해두는 식으로 했는데, 남은 일수를 함께 저장하다보니 결정적이지 못한 문제가 있었다 (테스트케이스는 무리없이 돌아갔지만 통과되진 않음)

 

질문 게시판 보니까 엄청 간단하게 푸셔서 당황..;

포인트는 해당 일에 저장하는 게 아니라 해당일의 상담이 끝나는 날에 가서 비교하는 것

지금 있는 상담을 하는 경우, 상담이 끝났을 날짜(target day)에, 상담을 함으로써 얻을 수 있는 수익과, 하지 않았을 때 그날(target day)의 수익을 비교하는 것.

 

그리고 이렇게만 하면 N일차 즉 마지막 날에 수익이 갱신되어 있지 않을 수 있기 때문에,

반복문으로 모든 날짜들을 순회하면서 처음에 무조건 그 전날까지의 수익과 해당 날의 현재 수익을 비교해서 큰 것을 저장해두어야 한다.

 

소스코드

import Foundation

func solution() -> Int {

    // input
    let N:Int = Int(readLine()!)!
    
    var T:[Int] = [0]
    var P:[Int] = [0]
    for _ in 1...N {
        let line = readLine()!.split(separator: " ").map { Int($0)! }
        T.append(line[0])
        P.append(line[1])
    }

    // process
    
    var dp:[Int] = Array<Int>(repeating: 0, count: N+1)
    
    for i in 1...N {
        if dp[i] < dp[i-1] {
            dp[i] = dp[i-1]
        }
        var targetDay = i+T[i]-1
        if targetDay <= N && dp[targetDay] < dp[i-1]+P[i] {
            dp[targetDay] = dp[i-1]+P[i]
        }
    }
    
    return dp[N]
    
}

print(solution())

 

 

이건 이전 버전 틀린 코드..아까워..

import Foundation

func solution() -> Int {

    // input
    let N:Int = Int(readLine()!)!
    
    var T:[Int] = [0]
    var P:[Int] = [0]
    for _ in 1...N {
        let line = readLine()!.split(separator: " ").map { Int($0)! }
        T.append(line[0])
        P.append(line[1])
    }

    // process
    var dp:[[C]] = Array<Array<C>>(repeating: Array<C>(repeating: C(), count: N+1), count: 2)
    
    // dp[상담여부][날짜] = 현재까지 수익, 남은 상담 날짜
    if N >= T[1] {
        dp[0][1] = C(date: T[1]-1, cost: P[1]) // 상담하는 경우
    } else {
        dp[0][1] = C(date: 0, cost: 0) // 상담 못하는 경우
    }
    dp[1][1] = C(date: 0, cost: 0) // 상담 안하는 경우

    
    for i in 2...N {
        var cost0 = dp[0][i-1].cost
        var date0 = dp[0][i-1].date
        var cost1 = dp[1][i-1].cost
        var date1 = dp[1][i-1].date
        // 오늘꺼 상담 하는 경우
        if N+1-i >= T[i] {
            if date0 > 0 && date1 > 0 {
                // 둘다 안됨 오늘 것만 상담
                dp[0][i] = C(date: T[i]-1, cost: P[i])
            } else if date0 > 0 && date1 == 0 {
                // 어제 상담 안한거에 추가
                dp[0][i] = C(date: T[i]-1, cost: cost1+P[i])
            } else if date0 == 0 && date1 > 0 {
                dp[0][i] = C(date: T[i]-1, cost: cost0+P[i])
            } else {
                // 둘다 가능 비용 큰거에 오늘거 추가
                if cost0 < cost1 {
                    dp[0][i] = C(date: T[i]-1, cost: cost1+P[i])
                } else {
                    dp[0][i] = C(date: T[i]-1, cost: cost0+P[i])
                }
            }
        } else {
            // 상담 못함 -> 이전날 결과 둘 중 큰거
            if cost0 < cost1 {
                dp[0][i] = C(date: date1 > 0 ? date1-1 : 0, cost: cost1)
            } else {
                dp[0][i] = C(date: date0 > 0 ? date0-1 : 0, cost: cost0)
            }
        }
        
        // 상담 안함 -> 이전날 결과 둘 중 큰거
        if cost0 < cost1 {
            dp[1][i] = C(date: date1 > 0 ? date1-1 : 0, cost: cost1)
        } else {
            dp[1][i] = C(date: date0 > 0 ? date0-1 : 0, cost: cost0)
        }
    }
    
    return max(dp[0][N].cost, dp[1][N].cost)
}

print(solution())