3814. [Professional] 평등주의

이번에도 parametric search 방법을 써서 풀어낸다. 이런곳에서도 쓰일수 있다는 느낌을 가지고 싶어서 작성.

솔직히 상식적으로 (2 ≤ N ≤ 100000, 1 ≤ K ≤ 109) 의 범위를 가지고 있는데, 정석대로 한다면 범위 K가 10억이라 도저히 안될 것 같았다. 그러니까 for i in range(k) 같은 것은 못쓴다. 100000까지는 무리없이 되기 때문에 N 크기만큼 for문을 써야 한다고 생각했다.

그럼 N만큼만 해서 어떻게 정답을 알아낼 수 있는가? 어떻하긴 계속 순회시키면서 정답을 때려 맞추는 수밖에..

여기서 주의할 테크닉은 양쪽과 비교한 크기이기 때문에 →쪽으로 순회와 ← 쪽으로 순회를 하는데 한번에 for문으로 넣었더니 의도대로 안되서 맘 편하게 for문을 2개 썻다. 어떻게 이게 문제인지 알아냈냐면 리스트 내의 원소 순서가 반전이 되도 결과는 똑같아야 되는데 결과가 다르게 나와서 눈치챘다.

이런식으로 주어진 테스트케이스로는 되는데 제출하면 안되는 경우가 너무 많다. 그래서 왜 틀렸나 점검하고 싶어도 스스로 만들어가며 점검해야 한다. 쉐도우복싱하는 느낌이다.. 

import sys

sys.stdin = open("sample_input.txt", "r")

def isAvailable(a,c,k):
    count = 0
    for i in range(len(a)-1):
        if a[i+1] - a[i] > c:
            count += a[i+1] - (a[i] + c)
            a[i+1] = a[i] + c
        # print(a,i,c,count,k)
        if count > k:
            return False
    for i in range(len(a)-1,0,-1):
        if a[i-1] - a[i] > c:
            count += a[i-1] - (a[i] + c)
            a[i-1] = a[i] + c
        # print(a, i, c, count, k)
        if count > k:
            return False
    return True

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    s = 0
    e = max(A)-min(A)
    while s < e:
        c = (s+e) // 2
        if isAvailable(A[:],c,K):
            e = c
        else:
            s = c + 1

    print("#{}".format(test_case),s)
    # ///////////////////////////////////////////////////////////////////////////////////