[백준 11058] 크리보드 (Swift)

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

 

DP

 

왜 디피는 여전히 어려운걸까

부분 문제로 열심히 머리굴리다가 안돼서 다른 블로그 참고했다.

결론은 점화식을 세우는 것이었음! - 간단해보이는 문제는 점화식으로 풀려고 했었던 것 같은데 오히려 이렇게 복잡해 보이는 문제는 더 점화식으로 풀 생각을 안하는 것 같음..

 

Key Idea는

- 우선 Ctrl-A, C, V를 한묶음으로 생각하기

- 비교대상을 A누르기 vs 복사하기 에서 A누르기 vs 1번 복사하기 vs 2번 복사하기 .. .. 로 확장해서 생각하기

였다.

 

점화식 세운 과정

dp[i] = max ( dp[i-3] * (1+1),

                       dp[i-4] * (2+1),

                       dp[i-5] * (3+1),

                       dp[i-6] * (4+1))

이걸 점화식을 세워보면 된다. (위 예시는 N이 7이라는 가정이라서 i-6 까지밖에 존재하지 않지만

실제로 비교해야하는 범위는 (i-3 ~ i-(N-1)) 까지 쉽게말해 1번째 ~ 현재위치에서 3칸 전 까지이다.

비교대상 위치를 J 라고 할 때, 뭘 비교하는거냐면, J 다음자리부터 ctrl+A 누르고 C 누르고 V 눌러서 i 에 도달할 때까지 계속 V 누르는 경우랑 비교하는 것 (복사한 후에는 그냥 A 붙이는것 보다 복사해둔거 붙여넣기 하는게 확실히 더 클테니까)

 

(근데 그럼 중간에 다시 복사하는건..고려안하는건지..)

흠 어쨌든 이렇게 점화식 세워서 풀면 코드가 아주 간단해지는데

 

소스코드

import Foundation

func solution() -> Int {
    let N:Int = Int(readLine()!)!
    
    var dp:[Int] = [Int](repeating: 0, count: N+1)
    
    for i in 1...N {
        dp[i] = dp[i-1]+1
        if i >= 3 {
            for j in 3..<i {
                dp[i] = max(dp[i-j]*(j-1), dp[i])
            }
        }
        
    }
    
    return dp[N]
}

print(solution())