백준 9465번 스티커 (swift) [S1]

다이내믹 프로그래밍(DP)

문제를 부분 문제로 나누어, 문제를 푼다.
메모이제이션 사용

생각회로

• 이번 스티커는 전 스티커의 영향을 받는다.
• 0 : 스티커를 떼지 않은 경우
• 1 : 위 스티커를 뗀 경우
• 2 : 아래 스티커를 뗀 경우

주의사항

• 아직 멍청해서 2차원 배열 선언을 헷갈렸다. 2행N열 vs N행2열
• 참고 ( https://m.blog.naver.com/kks227/220777103650 )

let T = Int(readLine()!)!
var N = 0
var dp = [[Int]]()
var li = [[Int]]()

func sticker(_ c:Int,_ status:Int)->Int{
    
    if c==N{ return 0 }
    if dp[status][c] != -1 { return dp[status][c]}
    
    var ret = sticker(c+1,0) // c번 열에서 아무것도 떼지 않은 경우
    
    if status != 1{ // 위에껄 떼지 않았다면,
        ret = max(ret,sticker(c+1,1)+li[0][c]) //이번에 위에 스티커를 뗀다. 위 스티커 점수 + 위 스티커 뗀 경우의 점수들
    }
    if status != 2{
        ret = max(ret,sticker(c+1,2)+li[1][c]) // 아래 스티커 점수 + 아래 스티커 뗀 경우의 점수
    }
    
    dp[status][c] = ret
    return ret
}


for _ in 0..<T{
    N = Int(readLine()!)!
    
    li = [[Int]]()
    dp = Array(repeating: Array(repeating: -1, count: N), count: 3)
    li.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    li.append(readLine()!.split(separator: " ").map{Int(String($0))!})

    print(sticker(0, 0))
}