백준 | 9461 파도반 수열 Swift - DP

이전 게시글에서 다이나믹 프로그래밍을 맛볼 수 있었는데,

한 발짝 더 나아가서 효율적으로 풀 수 있는 방법을 고민하는 문제가 여기 있다.

 

이전 게시글 보러가기 ⬇️

2023.07.18 - [공부하자!/알고리즘] - 백준 | 9095 1, 2, 3 더하기 Swift - DP

 

우선, 점화식을 구해보자!

문제에서 P(1)부터 P(10)까지 제공해주었다

1	2	3	4	5	6	7	8	9	10
1	1	1	2	2	3	4	5	7	9

그림에서 보면 알 수 있듯이,

11번째 삼각형의 한 변의 길이는 9+3, 즉 P(10)+P(6)인 12이다.

10번째 삼각형의 한 변의 길이는 P(9)+P(5)인 9이다.

즉 점화식을 구하면 다음과 같다

P(n) = P(n-1) + P(n-5)

 

하지만 이걸 그대로 코드로 구현하면 시간 초과가 뜬다!

주어지는 N의 범위가 <=100이기 때문에, P(100)을 하기 위해 수없이 많은 과정이 필요하기 때문!

P(100)
= P(99) + P(95)
= P(98) + P(94) + P(94) + P(90)
= P(97) + P(93) + P(93) + P(89) + P(93) + P(89) + P(89) + P(85) ...

숫자가 커질수록 중복되는 과정도 매우 많고,

재귀적으로 구현했을 때 함수 P를 불러오는 횟수가 매우매우 많아지기 때문에 더 좋은 방법을 생각해내야 한다.

 

여기에서 추가해볼 수 있는 기능은 바로 '저장해두기'!!!

만약 P(10)을 처음으로 구했을 때 어딘가에 저장해두었다면, 다시 P(10)을 위해 P(9)와 P(5)를 구하지 않아도 되도록 만드는 것이다!

이를 구현하기 위해 딕셔너리를 사용했다.

 

let t = Int(readLine()!)!

// P 함수 구현 후 구한 값을 저장해두는 딕셔너리
var pDict = [1:1, 2:1, 3:1, 4:2, 5:2]

// P 함수 구현
func P(_ n: Int) -> Int {
    var answer = 0
    
    if pDict[n] != nil { 	// pDict에 값이 있다면 바로 출력
        answer = pDict[n]!
    } else { 			// pDict에 값이 없다면 구한 후 출력
        pDict[n] = P(n-1) + P(n-5)
        answer = pDict[n]!
    }
    
    return answer
}

// 입출력 실행 부분
for _ in 0..<t {
    let n = Int(readLine()!)!
    print(P(n))
}