[백준] (Swift) 9465번 - 스티커 (dp 풀이)

문제 링크

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

9465번: 스티커

 

풀이 IDEA

이렇게 발견한 점화식은 아래와 같다. 여기서 dp 는 위에 그림으로 나타낸 최대값들을 저장하는 배열이고, arr 는 우리가 입력받은 스티커들의 가격이 명시되어있는 배열이다.

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

해당 점화식을 활용하여 문제를 풀면 된다.

 

소스코드  - 맞았습니다!

• 나는 sticker 라는 함수를 통해 dp 를 구성했다.
• 그리고 for 문을 이용해서 스티커들의 배열을 입력받았다.

let count = Int(readLine()!)!

for _ in 1...count {
    let n = Int(readLine()!)!
    var arr: [Array<Int>] = []
    for _ in 0...1 {
        let input = readLine()!.split(separator: " ").map { Int(String($0))! }
        arr.append(input)
    }
    
    let result = sticker(n: n, arr: arr)
    
    if n == 1 {
        print(max(result[0][0], result[1][0]))
    } else if n == 2 {
        print(max(result[0][1], result[1][1]))
    } else {
        print(max(result[0][n-1], result[1][n-1]))
    }
}


func sticker(n: Int, arr: Array<Array<Int>>) -> Array<Array<Int>> {
    var dp = Array(repeating: Array(repeating: 0, count: n), count: 2)
    dp[0][0] = arr[0][0]
    dp[1][0] = arr[1][0]
    
    if n > 1 {
        dp[0][1] = arr[1][0] + arr[0][1]
        dp[1][1] = arr[0][0] + arr[1][1]
        
        for i in 2..<n {
           dp[0][i] = max(dp[1][i-1] + arr[0][i], dp[1][i-2] + arr[0][i])
           dp[1][i] = max(dp[0][i-1] + arr[1][i], dp[0][i-2] + arr[1][i])
           
        }
    }
    return dp
}