14501번: 퇴사

문제 풀이 아이디어

- 자료구조/알고리즘
    : DP
- 풀이법
    1. 정의 : dp(i) = i일부터 N일까지 얻을 수 있는 최대 수익
    2. 구하는 답: dp(i)
    2. 초기값: dp(N) = pay[i] if cost[i] == 1 else 0 //👉 마지막 날일을 하루만에 할 수 있는지 확인
    3. 점화식
        if i + cost[i] - 1 > n: //🚫 그날 잡힌 상담을 할 수 없는 경우
            dp(i) = dp(i + 1) //👉 추가 없이 그대로
        else: //✅ 그날 상담을 할 수 없는 경우
            dp(i) = max(
								dp(i + 1), //👉 그날 상담 그냥 안하기
								pay[i] + dp(i + cost[i]) //👉 그날 상담하고 그 상담에 필요한 날에 번돈은 빼기
								)

보통 DP로 문제 해결을 할 때는 i가 작은 것 부터 해결하곤 하는데요. 이번 문제는 독특하게 i를 큰 수부터 구합니다. DP의 경우 점화식을 구할 때 그 이전까지는 어떻게 구했든지 관계 없이 i와 i + 1를 구하는 관계에만 집중해야 합니다.

하지만 이 문제를 앞에서 부터 접근할 경우 i까지는 퇴사날이 지나서 끝나서 할 수 없었던 일이 i + 1이 되면 할 수 있는 경우가 존재하게 됩니다. 이 경우 dp에 있는 값만으로는 점화식을 구할 수 없으며 일일히 경우의 수를 모두 따져봐야 합니다.

하지만 뒤에서 부터 접근할 경우 당장 i날에 추가된 일을 진행할 수 있지는지 없는지 따지고 만약 그 일을 할 수 있다면 그 일을 넣는 것이 좋은지 아닌지만 따지면 됩니다.

코드

// 입력 받기
let N = Int(readLine()!)!
var cost = [0]
var benefit = [0]
var cache = Array(repeating: -1, count: N + 1)

for _ in 0..<N {
    let line = readLine()!.split(separator: " ").map { Int(String($0))! }
    cost.append(line[0])
    benefit.append(line[1])
}

// 재귀함수로 dp 구현
func dp(_ i: Int) -> Int {
    // 퇴사일이 지나서는 일을 못한다.
    if i > N {
        return 0
    }
    
    // 초기값
    if i == N {
        cache[i] = cost[i] == 1 ? benefit[i] : 0
    }
    
    // 점화식
    if cache[i] < 0 {
        if i + cost[i] - 1 > N {
            cache[i] = dp(i + 1)
        } else {
            cache[i] = max(dp(i + 1), benefit[i] + dp(i + cost[i]))
        }
    }
    
    return cache[i]
}

print(dp(1))