백준 1351 - 무한수열 - swift

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

1351번: 무한 수열

 

선뜻보면 감이안온다. 

 

심지어 N이 1조이다. 

1부터 증가시켜서 찾을수도없다.

 

이 수열은 분명 재사용되는 값이 존재할 것 같지만, N이 1조안에서 dp를 적용해도 효율적일까 싶다.

결론은 효율적인데, 그 이유는 P와 Q의 범위를 보고 알 수 있다. 

P,Q는 최소 2이상이다. 

또한 수열특징이 P or Q로 나눈 값이다. 

 

즉, 최소 P,Q가 2라고 가정했을때, 매번 2로 나누어진다는 점이고, 이는 log2 로 계산할수있다. 

즉, log2 ( 1조 ) 는 약 39로, 39번의 횟수로 1조에서시작하여 0으로 도착하는걸 알 수 있다. 

2로 했는데도 39번이면, 값이 더 클수록 횟수는 훨씬더 줄어들것이다. 

 

물론 39번의횟수로 답을 찾는것은 아니고, 그보다는 더많은 횟수로 답을구하겠지만, dp를 적용한다면 훨씬 더 빠르게 구할 수 있을것이다. 

 

N이 1조이므로, 배열을 만들어서 dp적용하면 시간초과이므로, dictionary를 이용한다. 

 

let q = readLine()!.split(separator: " " ).map{Int(String($0))!}
let N = q[0], P = q[1], Q = q[2]
var dict = [0:1]

func dfs(_ n: Int ) -> Int {
    if let x = dict[n] {
        return x
    }
    dict[n] = dfs(n/P) + dfs(n/Q)
    return dict[n]!
}

print(dfs(N))