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

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

 

DP

N개의 곡마다 볼륨을 조정할 수 있는 크기가 주어진다. 무조건 그 곡을 연주할 때는 현재 볼륨에서 V[i] 를 빼거나 더한 볼륨으로 연주해야함

시작 볼륨이 주어지고 볼륨의 최대치가 주어질 때, 마지막 곡을 연주할 수 있는 가능한 최대 볼륨을 출력하는 문제

 

접근방법

이게 DP인지 완탐인지 모르게 풀이하긴 했다.

처음에는 2차원 배열에 볼륨을 올리는 경우와 내리는 경우를 저장해서, 최대값을 갱신하는 식으로 하려고 했는데, 뭔가 고려하지 못하는 경우의 수가 있을 것 같았다..저번에 퇴사 문제 풀 때도 이렇게 풀어서 틀렸던 기억

그래서 일직선에 0부터 M까지의 볼륨이 나타나있다고 가정하고, 시작 볼륨을 출발지라고 생각하면서

출발지로부터 볼륨을 더하고 빼서 현재 위치들을 표시해가는 식으로 풀이하면 될 것 같았다.

근데 이게 DP가 맞는지 모르겠다. 거의 모든 경우를 탐색하게 되는 것이 아닌가 싶긴하다..

 

아무튼 여기서도 2차원 배열을 사용하는데, 세로는 곡 리스트라고 보면 되고, 가로는 해당 곡에서 볼륨을 조정할 수 있는 이전 볼륨들의 집합이다. 

예를들어, 내가 현재 2번째 곡이라면 배열의 두번째 행은 V[2] 만큼의 볼륨을 내리거나 올릴 수 있는 이전 볼륨들의 집합인 거다.

그래서 그 볼륨들에 V[2]를 더하거나 뺐을 때 0~M 범위 내에 있는 볼륨이면 다음곡인 3번째 곡에 이전볼륨집합에 추가해준다.

볼륨들이 중복되어서 효율성이 낮아질 수 있기 때문에 스위프트 Set으로 선언했다.

 

소스코드

import Foundation

func solution() -> Int {
    //input
    let initi:[Int] = (readLine()?.split(separator: " ").map { Int($0)! })!
    let N = initi[0]
    let S = initi[1]
    let M = initi[2]
    
    let v:[Int] = (readLine()?.split(separator: " ").map { Int($0)! })!
    
    var dp:[Set<Int>] = [Set<Int>](repeating: [], count: N+1)

    //init
    dp[0].insert(S)
    
    //process
    for i in 0..<N {
        if dp[i].isEmpty {
            return -1
        }
        for cur in dp[i] {
            if cur-v[i] >= 0 {
                dp[i+1].insert(cur-v[i])
            }
            if cur+v[i] <= M {
                dp[i+1].insert(cur+v[i])
            }
        }
    }
    
    if dp[N].isEmpty {
        return -1
    } else {
        return dp[N].max()!
    }
}

print(solution())

 

아 찾아볼까 하다가 붙잡고 풀었는데 통과돼서 뿌듯하네!