문제 링크
문제 해설
문제만 보면 "그냥 등차 수열과 등비 수열을 set에 저장하고 크기를 출력하면 되는게 아닌가?" 싶지만 입력 범위에 함정이 있다. u의 범위가 \(10^{12}\)까지, 즉 1조라는 큰 숫자이기 때문에 a와 b가 1이고 u가 \(10^{12}\)이라면 등차 수열을 구하는데만 10,000초의 시간이 걸리게 될 뿐만 아니라 1조개의 Long타입을 set에 저장하게 되므로 7TB가 넘는 엄청난 양의 메모리를 차지하게 된다. 그렇기 때문에 좀 더 수학적인 방법의 접근이 요구된다. 1
등차 수열에 포함되는 1 이상, u 이하인 수의 개수는 나눗셈을 이용하면 바로 구할 수 있다. (코드의 4번째 줄) 등비 수열에 포함되는 1 이상, u 이하인 수의 개수는 직접 등비 수열을 계산하면서 카운트한다. \(n\) 이하인 등비 수열의 개수는 \(O(\log n)\)의 시간 복잡도로 구할 수 있으므로 u가 1조씩이나 된다고 해도 최대 40번의 계산만 하면 된다.(\(2^{40}=1,099,511,627,776>10^{12}\)이다.) 등비 수열을 계산할 땐 d가 1이면 c만 반복되기 때문에 c가 a보다 작거나 등차 수열에 포함되지 않을 때만 count를 증가시킨다. (코드의 5~6번째 줄의 if 블록) d가 1이 아니라면 등비 수열을 구하면서 등차 수열에 포함되지 않을 때만 count를 증가시킨다.
Code
fun main() = with(System.`in`.bufferedReader()) {
var (a, b, c, d, u) = readLine().split(' ').map { it.toLong() }
var count = 0L
if (a <= u) count = (u - a) / b + 1
if (d == 1L && c <= u) {
if (a != c && (a >= c || (c - a) % b != 0L)) count++
} else {
while (c <= u) {
if (c < a || (c - a) % b != 0L) count++
c *= d
}
}
println(count)
}
- 일반적으로 컴퓨터는 1초에 1억번의 연산을 할 수 있다고 가정한다. [본문으로]
'Algorithm > BOJ' 카테고리의 다른 글
[Kotlin] 백준 1456 : 거의 소수 (1) | 2022.12.23 |
---|---|
[Kotlin] 백준 25192 : 인사성 밝은 곰곰이 (0) | 2022.12.21 |
[Kotlin] 백준 9935 : 문자열 폭발 (0) | 2022.12.19 |
[Kotlin] 백준 1806 : 부분합 (0) | 2022.12.17 |
[Kotlin] 백준 25916 : 싫은데요 (0) | 2022.12.16 |
댓글