[Swift][DP] 백준 14051번 (퇴사)

요구능력 : DP에 대한 이해

 

코드설명 : 

 

이 문제는 삼성SW역량테스트? 거기서 나온문제라고 한다.

 

1. 입력받기

let n = Int(String(readLine()!))!
var t: [Int] = Array(repeating: 0, count: n + 1)
var p: [Int] = Array(repeating: 0, count: n + 1)
var dp = Array(repeating: 0, count: 1001)

for i in 1...n {
    let TP = readLine()!.split(separator: " ").map{Int(String($0))!}
    t[i] = TP[0]
    p[i] = TP[1]
    dp[i] = p[i] //넣어놔야 아래코드에서 비교가능
}

 

2. DP코드 짜기

for i in stride(from: n, through: 1, by: -1){
    if t[i] + i <= n + 1{
        dp[i] = max(dp[i + 1], dp[i + t[i]] + p[i]) //1.
        //dp[i + t[i]] + p[i]는 뒤에서부터 일한거 쌓이는거 누적
        //dp[i + 1]는 오늘 일해서 쌓이는거보다 다음날 일하는게 더크면 다음날꺼 쓴다는의미
    }else {
        dp[i] = dp[i + 1]
    }
}

우선, 왜 for문을 역순으로 돌렸는지부터 알아보자.

for문을 역순으로 돌리지 않으면 답찾기가 까다로웠다.

이유인 즉슨, 내가 구하고자하는 날짜인 n을 넘어가버리는 경우 때문이다.

 

1부터 돌릴경우, 7일에 있는 200이 보일것이다.

이 부분을 어떻게 처리해봐도 91퍼센트에서 틀린다. 내가이렇게하다 계속틀려서 멘탈이터졌다.

그 이유는 앞에 있는 dp[]에 결국 저 200이라는 숫자가 더해지기 때문인거같다.

 

역순으로 돌릴경우, 7일에 있는 200이 먼저 처리된다.

위의 코드에서 if문을 통과하지 못하고 dp[7] = dp[8] (dp[8]은 0이다.)이 되기 때문이다.

맨 마지막의 성가신 조건을 먼저 처리하고나면 점화식은 구하기 수월하다.

 

조건이 충족을 못 할경우에,

dp[i] = dp[i + 1] 로 해놨는데 그 이유는 퇴사일을 넘어가는 수들은 건너뛰기 위함이다.

거꾸로 가니까 dp[i + 1]은 이전 dp를 넣어준것이다.

예를들면 6일에 7일의 dp를 넣어준것이다.

왜냐하면 스케쥴을 소화하지 않더라도 이전스케쥴의 값을 가져와야 연속적으로 진행이 되기때문.

 

점화식을 설명하면, dp[i + 1]은 오늘의 스케쥴을 소화하지 않았을 때 그냥 날짜를 한칸 넘어간다는 의미이고,

dp[i + t[i]] + p[i] 는 만약 오늘의 스케쥴을 소화했다면 스케쥴을 소화하기까지 걸린 dp에 구해져있는값(이전까지의 p의 합)과 오늘 소화한 스케쥴인 p를 더해주면된다.

 

역순으로 보자.

백준은 7일에 상담을 할 수 없다.

이유는 7일에 상담하는 시간이 2일 걸리기 때문이다.

 

백준은 6일에 상담을 할 수 없다.

이유는 6일에 상담하는 시간이 4일 걸리기 때문이다.

 

백준은 5일에 상담을 할 수 있다.

이유는 5일에 상담하는 시간이 2일걸려서 6일에 상담이 끝나기 때문이다.

6일에 끝나고나면 7일로 넘어가는데 그럼 백준은 5일과 7일을 더 한 값을 갖게된다.

dp[5] = 15

 

백준은 4일에 상담을 할 수 있다.

이유는 1일 걸리기 때문이다.

4일에 끝나고나면 5일로넘어가는데 5일에는 이미 15가 들어가있다.

dp[4] = 20 + 15

 

백준은 3일에 상담을 할 수 있다.

이유는 1일 걸리기 때문이다.

3일에 끝나고나면 4일로 넘어가는데 4일에는 이미 35가 들어있다.

dp[3] = 10 + 35

 

백준은 2일에 상담을 할 수 있다.

이유는 5일 걸리기 때문이다

2일에 끝나고나면 7일로 넘어가는데 7일에는 0이 들어있다.

dp[2] = 20 + 0

 

백준은 1일에 상담을 할 수 있다.

이유는 3일 걸리기 때문이다.

3일에 끝나고나면 4일로 넘어가는데 4일에는 이미 35가 들어있다.

dp[1] = 10 + 35

 

가장 많은 페이를 받는 값은 45이다.

 

이거 보고 이해가 안가면 참고하시길.. 설명 진짜잘해주신다.

 

후기 : 이게 실버3티어 문제가 맞나....

현타씨게온다

let n = Int(String(readLine()!))!
var t: [Int] = Array(repeating: 0, count: n + 1)
var p: [Int] = Array(repeating: 0, count: n + 1)
var dp = Array(repeating: 0, count: 1001)

for i in 1...n {
    let TP = readLine()!.split(separator: " ").map{Int(String($0))!}
    t[i] = TP[0]
    p[i] = TP[1]
    dp[i] = p[i]
}

for i in stride(from: n, through: 1, by: -1){
    if t[i] + i <= n + 1{
        dp[i] = max(dp[i + 1], dp[i + t[i]] + p[i])
    }else {
        dp[i] = dp[i + 1]
    }
}
print(dp.max()!)