[Kotlin] 백준 14277 : 등차 수열과 등비 수열

문제 링크

14277번: 등차 수열과 등비 수열

---

 

---

문제 해설

문제만 보면 "그냥 등차 수열과 등비 수열을 set에 저장하고 크기를 출력하면 되는게 아닌가?" 싶지만 입력 범위에 함정이 있다. u의 범위가 \(10^{12}\)까지, 즉 1조라는 큰 숫자이기 때문에 a와 b가 1이고 u가 \(10^{12}\)이라면 등차 수열을 구하는데만 10,000초의 시간이 걸리게 될 뿐만 아니라^[각주:1] 1조개의 Long타입을 set에 저장하게 되므로 7TB가 넘는 엄청난 양의 메모리를 차지하게 된다. 그렇기 때문에 좀 더 수학적인 방법의 접근이 요구된다.

 

등차 수열에 포함되는 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초에 1억번의 연산을 할 수 있다고 가정한다. [본문으로]