이번 문제는 난이도가 좀 있습니다.
문제
문제의 본질:
주어진 배열 N에 대하여 양 옆의 요소에 대하여 차이를 1 이하로 유지하며 주어진 K개의 블록을 최대 높이를 쌓기
가 아니라
차이가 1 이하인 주어진 배열을 기반으로한 결과물만 있으면 됩니다.
1씩 증가시킨다는 조건은 중요치 않습니다. N보다 낮아지지 않으면 되는거고 K개를 쓰기만 하면 됩니다. 중간 과정은 스킵해도 문제가 없습니다.
제약 조건
1≤N≤100000
1≤K≤1018
모든 i (1≤i≤N)에 대해, 1≤Hi≤109
Subtask1 (10점): N≤100, K≤1,000
Subtask2 (20점): N≤1,000, K≤10,000
Subtask3 (30점): N≤1,000
Subtask4 (40점): 추가 제약 조건 없음
풀이 1
이 풀이는 일단은 60점입니다. subtask 40을 통과 하지 못하지만 이분 탐색을 어려워하시는 분들이 보면 좋을것같아서 작성했습니다.
# 입력 제어
import sys
input=sys.stdin.readline
n,k=map(int,(input().split()))
h_list=list(map(int,(input().split())))
# index i에 높이 h 만큼 추가로 쌓아 올릴 수 있나 (h는 k이하)
def is_able(i,h,n,k):
before_height=h_list[i]+h
total_blocks=h
# 좌측에 필요한 추가블럭수
for left in range(i-1,-1,-1):
now_height=h_list[left]
# 변화가 없다면 그 다음도 채크할 필요없다
if abs(now_height-before_height)<=1:
break
# 최소한으로 블럭 사용 - 한칸 차이나게 세팅
total_blocks+=(before_height-1-now_height)
before_height-=1
# 조건을 초과 하면 k
if total_blocks>k:
return False
# 우측은 상동
before_height=h_list[i]+h
for right in range(i+1,n):
now_height=h_list[right]
if abs(now_height-before_height)<=1:
break
total_blocks+=(before_height-1-now_height)
before_height-=1
if total_blocks>k:
return False
return True
# 이분 탐색
def find_able_height(i,left,right,n,k):
while left<=right:
mid=(left+right)//2
if is_able(i,mid,n,k):
left=mid+1
else:
right=mid-1
return left-1
answer=max(h_list)
for i in range(n):
need_block=answer-h_list[i]
if need_block < 0:
continue
if is_able(i,need_block+1,n,k):
best_add=find_able_height(i,need_block+1,k,n,k)
answer=h_list[i]+best_add
print(answer)
이 정도면 잘 풀었다 싶었지만 시간초과가 생깁니다.
그렇다면 해결책은 뭘까 생각해봅니다.
이분 탐색은 문제없어 보이고 그러면 저 is_able함수를 더 짧게 만들어야겠다 싶습니다.
개념정리
기둥 j 가 높이 i가 되기위해 피라미드 모양을 갖추기 위한 필요한 기둥수는 다음과 같습니다.
이 식을 바탕으로 아무 i중 하나에서만 K보다 작으면 됨으로 다음과 같은 식을 만족하면 됩니다.
이 탠트 모양의 함수를 구하는 가장 쉬운 방식은 결국
"차분 배열(누적합)” 기법을 사용하여 모든 𝑖 에 대해 빠르게 합산하는 것 입니다.
자세한내용은 주석안에 써두었습니다.
코드
import sys
input = sys.stdin.readline
def can_achieve(X, N, K, H):
"""
X : 후보 꼭대기 높이
N : 기둥 수
K : 최대 연산 횟수
H : 초기 기둥 높이 (0-indexed)
각 j(1-indexed)에 대해, r = X - H[j-1] (r > 0인 경우에만)
기둥 j가 만드는 텐트함수 f_j(i)= max(0, r - |i-j|)는
- i in [L, j] : f_j(i) = i - j + r
- i in [j, R] : f_j(i) = - i + (r + j)
(여기서 L = max(1, j - r + 1), R = min(N, j + r - 1))
두 구간이 겹치는 i=j에서 r가 두 번 더해지므로, 한 번 빼줍니다.
이 구간별 선형함수 덧셈은 차분 배열 기법을 사용해 전체 i (1~N)에 대해 F(i)를 계산합니다.
최종적으로 min_{i} F(i)가 K 이하이면 X를 만들 수 있다.
"""
size = N + 3
diff_a = [0] * size # i에 곱해지는 계수용 차분 배열
diff_b = [0] * size # 상수항 차분 배열
# j: 1-indexed로 처리 (H는 0-indexed)
for j in range(1, N+1):
r = X - H[j-1]
if r <= 0:
continue
L = j - r + 1
if L < 1:
L = 1
R = j + r - 1
if R > N:
R = N
# [L, j] 구간에 대해, 함수 f(i)= i - j + r
if L <= j:
diff_a[L] += 1
diff_a[j+1] -= 1
diff_b[L] += (r - j)
diff_b[j+1] -= (r - j)
# [j, R] 구간에 대해, 함수 f(i)= - i + (r + j)
if j <= R:
diff_a[j] += -1
diff_a[R+1] -= -1 # == diff_a[R+1] += 1
diff_b[j] += (r + j)
diff_b[R+1] -= (r + j)
# i = j에서 중복된 r 한 개를 빼준다.
diff_b[j] -= r
diff_b[j+1] += r
best = 10**20 # 매우 큰 수
curr_a = 0
curr_b = 0
# 차분배열을 prefix sum하여 각 i(1-indexed)에 대해 F(i) 계산
for i in range(1, N+1):
curr_a += diff_a[i]
curr_b += diff_b[i]
cost = curr_a * i + curr_b
if cost < best:
best = cost
return best <= K
# 입력 읽기
N, K = map(int, input().split())
H = list(map(int, input().split()))
Hmax = max(H)
# 이분탐색으로 최대 X (탑의 높이)를 구합니다.
# 최소 X는 이미 존재하는 최대 높이, 최대 X는 한 기둥에 모두 올린 경우.
lo = Hmax
hi = Hmax + K
while lo < hi:
mid = (lo + hi + 1) // 2
if can_achieve(mid, N, K, H):
lo = mid
else:
hi = mid - 1
sys.stdout.write(str(lo) + "\n")
정말 어렵습니다. 이번 껀 꼭 손으로 직접 단계별로 해보시고 이해를 하시는걸 추천드립니다.
