[Swift][DP] 백준 1495번 (기타리스트)

요구능력 : DP활용

 

코드설명 : 

 

문제에서의 핵심

현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

 

점화식

dp[i][j] = i는 몇번째 곡 인지, j는 볼륨이다.

dp[3][4] = true 이면 3번째곡에서 4의 볼륨을 공연할수 있다는 의미이다.

 

후기 : dp에 true/false를 넣는것부터 참신한 문제..?인것같다. 

진짜 점화식만 잘세우면 푸는문제..

let nsm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nsm[0] //연주할 곡의 개수
let s = nsm[1] // 시작볼륨
let m = nsm[2] // 최대볼륨

let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: Array(repeating: false, count: 1001), count: 51)
if s + arr[0] <= m {
    dp[1][s + arr[0]] = true
}
if s - arr[0] >= 0 {
    dp[1][s - arr[0]] = true
}


for i in stride(from: 2, through: n, by: 1){
    for j in 0...m{
        if dp[i - 1][j]{
            if j - arr[i - 1] >= 0 {
                dp[i][j - arr[i - 1]] = true
            }
            if j + arr[i - 1] <= m {
                dp[i][j + arr[i - 1]] = true
            }
        }
    }
}
var idx = -1
for i in stride(from: m, through: 0, by: -1){
    if dp[n][i]{
        idx = i
        break
    }
}
print(idx)