이번 글에서는 숫자 l과 단조 증가(monotonic increasing) 수열 f(m)이 주어졌을 때, f(m) = l을 만족하는 m 값을 찾는 방법을 다룹니다. 여기서 함수 f(m)은 다음과 같이 정의됩니다.
f(m) = am + bm·[log2(m)] + cm³
단, a = 1, 2, 3, … / b = 1, 2, 3, … / c = 0, 1, 2, 3, … 이며, [log2(m)]은 밑이 2인 로그값을 내림(버림)한 정수입니다.
[log2(m)]의 계산 방식
내림 연산이 적용되므로 m의 구간에 따라 값이 다음과 같이 결정됩니다.
- m = 1 → 값은 0
- m = 2 ~ 3 → 값은 1
- m = 4 ~ 7 → 값은 2
- m = 8 ~ 15 → 값은 3
이런 식으로 구간이 커질수록 로그값도 하나씩 증가합니다.
문제 정의
우리가 해야 할 일은 f(m) = l을 만족하는 m을 찾는 것입니다. 만약 l이 수열에 존재하지 않는다면 0을 출력해야 합니다. 주의할 점은 모든 값이 64비트로 표현 가능해야 하며, 세 정수 a, b, c는 각각 100 이하라는 조건입니다.
예를 들어 입력이 a = 2, b = 1, c = 1, l = 12168587437017이라면 출력은 23001입니다. 실제로 f(23001) = 12168587437017이 성립하기 때문입니다.
해결 접근 방법
함수 f(m)은 단조 증가하므로 이진 탐색(binary search)을 활용하면 효율적으로 답을 구할 수 있습니다. 알고리즘은 다음과 같습니다.
- 탐색 상한 SMALLER_VAL := 1,000,000으로 설정
- c가 0일 경우 함수의 증가 속도가 느려지므로 상한을 LARGER_VAL := 1,000,000,000,000,000으로 확장
- 주어진 a, b, c, n에 대해 f(n)을 계산하는 solve() 함수 정의
- ans := a × n
- lg_val := log2(n)의 내림값
- ans := ans + b × n × lg_val
- ans := ans + c × n³
- ans 반환
- 메인 로직에서 이진 탐색 수행
- begin := 1, end := 탐색 상한값
- begin ≤ end 동안 반복:
- mid := (begin + end) ÷ 2 (정수 부분만)
- val := solve(a, b, c, mid)
- val == k이면 ans := mid 저장 후 종료
- val > k이면 end := mid − 1
- 그 외에는 begin := mid + 1
- 반복 종료 후 ans 반환 (찾지 못하면 0)
구현 예제
아래는 위 알고리즘을 Python으로 구현한 코드입니다.
from math import log2, floor
SMALLER_VAL = 1000000
LARGER_VAL = 1000000000000000
def solve(a, b, c, n):
ans = a * n
lg_val = floor(log2(n))
ans += b * n * lg_val
ans += c * n**3
return ans
def get_pos(a, b, c, k):
begin = 1
end = SMALLER_VAL
if c == 0:
end = LARGER_VAL
ans = 0
while begin <= end:
mid = (begin + end) // 2
val = solve(a, b, c, mid)
if val == k:
ans = mid
break
elif val > k:
end = mid - 1
else:
begin = mid + 1
return ans
a = 2
b = 1
c = 1
k = 12168587437017
print(get_pos(a, b, c, k))입력
a = 2, b = 1, c = 1, k = 12168587437017
출력
23001
정리
이 문제의 핵심은 f(m)이 단조 증가한다는 성질을 이용해 선형 탐색 대신 이진 탐색을 적용하는 것입니다. 덕분에 최대 10¹⁵까지의 범위에서도 O(log n) 시간 복잡도로 빠르게 답을 찾을 수 있습니다. 특히 c = 0일 때는 함수의 증가 폭이 작아지므로 탐색 범위를 넓혀야 한다는 점이 중요한 포인트입니다.