본문 바로가기
  • 개발하는 곰돌이
Algorithm/BOJ

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

by 개발하는 곰돌이 2022. 12. 21.

문제 링크

 

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

예제 4의 경우에 4, 20, 100, 452, 476, 500, 524, 548, 572, 596이 정답이다.

www.acmicpc.net


 


문제 해설

문제만 보면 "그냥 등차 수열과 등비 수열을 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억번의 연산을 할 수 있다고 가정한다. [본문으로]

댓글