[백준] (Swift) 9095번 - 1,2,3 더하기 (스위프트 다이나믹 프로그래밍 풀이)

문제 링크

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

9095번: 1, 2, 3 더하기

 

내가 푼 풀이 - 맞았습니다!

dp 문제를 세 번째 푸는 것이지만, 감을 아직 잡지 못했따. (바본가) 그래서 풀이를 찾아보던 중, dp 문제는 규칙을 찾아내는 거싱 핵심 포인트가 된다는 점을 알게 되었다. dp 문제 특성상, 경우의 수를 찾는 문제가 많고, memoization 해놓은 바로 직전의 수열에 더해서 값을 찾아내는 문제가 많기 때문이다.

내가 해당 문제를 풀이한 방법은 다음과 같다. *(필기에 오류가 있어서 수정했슴다 허허)

이렇게 일단 1 부터 쭉 경우의 수를 살펴보면, dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이라는 규칙을 발견하게 된다.
따라서 dp[0], dp[1], dp[2], dp[3] 까지 임의의 숫자를 넣어준 뒤, 4 부터는 해당 수식에 맞게 경우의 수를 구하면 된다.이를 코드로 구현하면 아래와 같다.

let n = Int(readLine()!)!

for _ in 0..<n {
    let num = Int(readLine()!)!
    var dp = [Int](repeating: 0, count: num+1)
    
    if num == 1 {
        print(1)
    } else if num == 2 {
        print(2)
    } else if num == 3 {
        print(4)
    } else {
        dp[1] = 1
        dp[2] = 2
        dp[3] = 4

        for i in 4..<num+1 {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        }
        print(dp[num])
    }

}

 

dp 문제는 우선 딱보면 "아, dp 구나" 를 알정도로 연습이 필요한 것 같다. dp 임을 발견하는 순간, 문제를 풀이하는 방식에 대해서는 거의 대부분 동일하게 풀이되므로, 역시 문제는 많이 풀어보고 감을 익히는 것이 중요할 것 같다.

그리고 dp 문제를 접했을 때는 규칙을 먼저 찾으려고 노력해보자!