백준 1351 - 무한수열 - swift
https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 선뜻보면 감이안온다. 심지어 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로 했는데도 ..
2021. 6. 24.