Skip to content

[Algorithm] 1, 2, 3 더하기 #186

@hwangJi-dev

Description

@hwangJi-dev

💬 문제

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

이 문제는 DP의 기본문제라고 할 수 있다.

그치만 아직 DP가 익숙하지 않아서 점화식이 바로바로 떠오르지가 않았기에 깊게 고민이 필요했다. 하 뭔가 알 것 같은데.. 규칙이 보일 것 같은데, 머릿속에서 얽혀버려서 결국 다른 풀이를 참고했다.

풀이를 참고하고 보니 접근법까지는 맞았는데,, 1, 2, 3의 합으로 나타내는 이라는 중요한 key point를 놓치고 있었다. 진짜 DP는 풀이를 참고하면 할수록 신세계인 것 같다 .. 어떤 분이 블로그에 고민하다가 보는 DP 풀이는 정말 신세계고 그런걸 많이많이 경험해보라 하셨는데 너무너무 공감이 간다 ㅎㅎ

이 풀이를 참고하시는 여러분도 DP의 신세계를 경험하는데 조금이나마 도움이 되길 바라며 풀이를 올려보겠습니다!


💬 Idea

  • 바텀업 방식으로 DP를 구현

  • 💬 풀이

    import Foundation
    

    func solution9095() {
    let TC = Int(readLine()!)!
    var sumCaseArr = Array(repeating: 0, count: 11)

    sumCaseArr[1] = 1
    sumCaseArr[2] = 2
    sumCaseArr[3] = 4
    
    for i in 4...10 {
        sumCaseArr[i] = sumCaseArr[i - 1] + sumCaseArr[i - 2] + sumCaseArr[i - 3]
    }
    
    for _ in 0..<TC {
        let n = Int(readLine()!)!
        print(sumCaseArr[n])
    }
    

    }

    DP.. 간단한 문제인데도 참 어렵네요!!

    그렇지만 중요한건 꺾이지 않는 마음이겠죠 😊😊

Metadata

Metadata

Assignees

Labels

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions