[Swift] BOJ 9095 1,2,3더하기

BOJ 9095 1,2,3더하기

 

✅ BOJ 9095 1,2,3 더하기

 

백준 문제는 뭔가 센스도 좋아야할듯

프로그래머스는 풀 때 자료구조랑 알고리즘 생각하면서 풀면 그래도 풀리는데 백준 문제는 정말 한계가 없음.

처음 이거 풀때는 답도 안보였는데, 구글링 해보니까 문제가 엄청 쉽더라.

그냥 하나하나 손케이스 하면 되는거.

 

예전에 수능 푸는 느낌이라서 조금 더 학습해야겠다!

 

✅ 알고리즘 접근법

1 -> 1개

2 -> 2개

3 -> 3개

4 -> 7개

5 -> 13개 

이렇게 나아가는데, dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 으로 점화식을 가짐.

 

        let input: Int! = Int(readLine()!) // 케이스 개수
        var list = [Int]() // 케이스
        
        for _ in 0..<input {
            list.append(Int(readLine()!)!)
        }
        
        var dp = [Int](repeating: 0, count: 10)
        dp[0] = 1
        dp[1] = 2
        dp[2] = 4
        
        list.forEach {
            if $0 > 2 {
                for i in 3..<$0 {
                    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
                }
            }
            print(dp[$0-1])
        }