[PS] BOJ 31963 / 두 배
![[PS] BOJ 31963 / 두 배](/content/images/size/w2000/2025/10/-------------3.png)
문제 링크: https://www.acmicpc.net/problem/31963
그리디한 접근으로 풀 수 있는 문제입니다. 단, 수의 크기가 굉장히 크기 때문에 시간 초과를 피하기 위해서는 요령이 필요합니다.
풀이
간단한 구현
수열을 오름차순으로 만들기 위해서, $A$의 $i$번 원소 A[$i$] (단, $1 \leq i \leq N$)를 2배로 만드는 연산을 원하는 만큼 할 수 있습니다. 수열을 오름차순으로 만들기 위한 최소 연산 횟수를 구해야 합니다.
간단하게, $i$ ($2 \leq i \leq N$) 에 대해, $i-1$번 원소보다 커질 때 까지 2를 곱해보며 횟수를 셀 수 있습니다.
input = open(0).readline
N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(1, N):
while A[i] < A[i - 1]:
A[i] *= 2
cnt += 1
print(cnt)
간단한 구현
간단한 구현의 문제 - 시간 초과
문제 조건을 다시 봅시다.
- $1 ≤ N ≤ 250\, 000$
- $1 ≤ A_i ≤ 1\, 000\, 000$ ($1 ≤ i ≤ N$)
위의 구현대로면, A[$i$]가 내림차순으로 주어지는 경우 반복 횟수가 늘어나고, 인접한 두 수의 차가 커질수록 반복 횟수가 늘어나니, 데이터에 따라서는 시간 초과가 일어납니다.
실제로, 서브태스크 5에 주어지는 입력 조건이 내림차순입니다.
| 번호 | 배점 | 제한 |
|---|---|---|
| ... | ... | ... |
| 5 | 20 | 각 $i$ ($1 ≤ i ≤ N - 1$)에 대해, $A_i ≥ A_{i+1}$ |
그렇다면, 반복문을 사용하지 않고 연산 횟수를 계산할 방법은 없을까요?
로그를 사용한 풀이
A[$i$]가 A[$i-1$]보다 커지기 위해서는, A[$i$]에 곱하는 수 $k$ ($k$는 2의 거듭제곱)가 $A[i-1] / A[i]$보다 크거나 같아야 합니다.
또, A[$i$]에 취할 수 있는 연산은 오로지 2를 곱하는 것 뿐이니, $log_2$를 취해 수를 더 작게 다룰 수 있습니다.
from math import log2, ceil
cnt = 0 # 2를 곱하는 연산의 최소 횟수를 기록
prev = 0 # 바로 이전 원소에 2를 곱하는 연산을 수행한 "만큼의" log2값 (A배열을 직접 변경하지 않기 위함)
for i in range(1, N):
# 앞의 수와의 크기 차이를 log2로 계산
# 앞의 수보다 커지려면 2를 몇 번 곱해야 하는지의 값이 된다.
cur_log = log2(A[i - 1] / A[i])
# 이전 원소는 A에 저장된 상태에 추가로 2를 곱했을 수 있기 때문에, 그 크기의 log2값을 prev에 저장하고 다음 원소 계산에 사용한다.
res = ceil(cur_log) + prev
if res > 0: # res > 0일때는 2를 양수 번 곱한 것.
cnt += res
prev = res # A[i]가 커졌으니 커진만큼 prev를 반영
else: # 이미 A[i]가 A[i-1]보다 크거나 같으므로, A[i]에 2를 곱하지 않음
prev = 0 # A[i]값과 동일하니 prev는 0이다.log2를 활용한 계산
전체 코드
from math import log2, ceil
input = open(0).readline
N = int(input())
A = list(map(int, input().split()))
cnt = 0
prev = 0
for i in range(1, N):
cur_log = log2(A[i - 1] / A[i])
res = ceil(cur_log) + prev
if res > 0:
cnt += res
prev = res
else:
prev = 0
print(cnt)
solution.py