[백준] (Swift) 14501번 - 퇴사 (두번째 풀이, DP)

🟠 문제

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

14501번: 퇴사

🟠 문제 풀이

이전에 봤던 문제였던게 기억났다. 문제는 딱 보자마자 dp 임을 파악 할 수 있었다. 내가 평소에 좋아하던 dp 유형이었다!

이렇게 풀이를 생각해내고, 아래와 같은 코드를 작성했다.

let n = Int(readLine()!)!
var arr = [[0, 0]]
for _ in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}
var dp = Array(repeating: 0, count: 21) // 최대 N -> 15일, 상담 term 최대 5일

for i in 1..<n+1 {
    if i+arr[i][0] > n {
        continue
    }
    dp[i+arr[i][0]] = max(arr[i][1] + dp[i], dp[i])
}

print(dp.max()!)

이렇게 푸니까 틀렸다고 뜨는 것이다.... 왜지??

곰곰히 생각해보니까, 아래와 같은 경우를 나는 판단하지 않았다. 4일차에 새로운 상담을 진행하지 않고, 이전의 값이 유지되는게 더 큰 경우를 생각하지 않았던 것이다.

이런 경우까지 모두 포함시켜서 코드를 작성해주어야했다. 다음ㄴ

let n = Int(readLine()!)!
var arr = [[0, 0]]
for _ in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}
var dp = Array(repeating: 0, count: 21) // 최대 N -> 15일, 상담 term 최대 5일

for i in 1..<n+1 {
    if i+arr[i][0] > n+1 {
        continue
    }

    if dp[i] > dp[i+1] {
        dp[i+1] = dp[i]
    }

    dp[i+arr[i][0]] = max(arr[i][1] + dp[i], dp[i+arr[i][0]])
}
print(dp.max()!)

이렇게 가운데 if 문을 추가해주었다. 내일의 금액이 오늘의 금액보다 작으면, 오늘의 금액을 그대로 이월(?)해서 가져가면 되기 때문에 dp[i+1]에 dp[i]를 넣어주었다.

여기서 또 틀렸다.... 왜... 도대체 또 왜 .. 뭐가문젠데... 자세히 살펴보니까, 첫번째 if문이 문제였다. for문에 진입하자마자 if를 통해서 n+1이 넘어가는지 판단을 해주고, 넝을경우 continue해서 해당 i를 처리하지 않도록 해줬다. 하지만, 이것은 만약 n+1을 넘더라도, dp[i]는 처리할 수 있도록 해주어야하는데, 이 모든 과정을 날려먹기 때문에 결과값이 다르게 나올 수 밖에 없다. 그래서 if 문의 순서를 바꿔줘야 했다. (바꾸니까 정답이다!) 

🟠 정답코드

아,, 중간중간 인덱스 관련해서 오류도 많았고, 이것저것 if문에 대해서 생각하지 못한 부분...이 많았어서 굉장히 많이 틀렸다. ㅋㅋㅋㅋㅋ 하... 두번째 풀이인데 왤케 쩔쩔매는거지 하지만 그래도 해냈다!

import Foundation

let n = Int(readLine()!)!
var arr = [[0, 0]]
for _ in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}
var dp = Array(repeating: 0, count: 100)

for i in 1..<n+1 {
    if dp[i] > dp[i+1] {
        dp[i+1] = dp[i]
    }

    if i+arr[i][0] > n+1 {
        continue
    }

    dp[i+arr[i][0]] = max(arr[i][1] + dp[i], dp[i+arr[i][0]])
}

print(dp.max()!)

 

dp.max()!값을 뽑지 않고, dp[n+1]값을 뽑아도 된다~