[Swift 백준] 1535 안녕

 

풀이 아이디어

dp로 풀이했습니다.

점화식을 적으려다보니 너무 가독성이 떨어져서 

자세한 설명은 코드에 적어놓겠습니다

풀이

let n = Int(readLine()!)!
let minusHP = readLine()!.split(separator: " ").map { Int($0)! } // 체력 소모량
let plustHappy = readLine()!.split(separator: " ").map { Int($0)! } // 기쁨 증가량

var dp = [Int](repeating: 0, count: 101)

for i in 0..<n {
    let hp = minusHP[i]
    let happpy = plustHappy[i]
    
    // 체력이 100부터 현재 health까지 역순으로 탐색
    for j in stride(from: 100, through: hp, by: -1) {
        dp[j] = max(dp[j], dp[j - hp] + happpy)
    }
    /*
    stride(from: 100, through: hp, by: -1):
    체력 j는 100에서부터 해당 아이템의 체력 소모량 hp까지 역순으로 탐색.
     역순인 이유는, 한 번의 탐색에서 현재 상태를 갱신하면서 다른 상태에 영향을 미치지 않도록 하기 위함.
    */
    
    /*
     점화식
     체력이 j일 때의 최대 기쁨을 구함. 두 가지를 비교:
     dp[j]: 현재 체력 j에서 얻을 수 있는 기쁨
     dp[j - hp] + happy: 인사를 했을 경우, 이전 체력 j - hp에서 얻을 수 있는 최대 기쁨에 기쁨 증가량 happy를 더한 값.
    */
}

// 체력을 99까지 쓸 수 있을때의 결과 출력
print(dp[99])