3813. [Professional] 1일차 - 그래도 수명이 절반이 되어서는

원래 정직하게 찾으면 N^3 정도는 나올 것 같은데 거꾸로 정답을 가정하고 찾아가는 방법을 써서 NlogN으로 줄었다고 한다.

다른 사이트들을 보고 참고했다. 특히 코드는 그대로 따라함.

# https://ggodong.tistory.com/90
# https://herong.tistory.com/entry/SWEA-3813-%EA%B7%B8%EB%9E%98%EB%8F%84-%EC%88%98%EB%AA%85%EC%9D%B4-%EC%A0%88%EB%B0%98%EC%9D%B4-%EB%90%98%EC%96%B4%EC%84%9C%EB%8A%94

일단 주어진 배열에서 "이 값이면 정답일까?" 하고 배열에서 최소값과 최대값의 중간값을 가정하고 풀어나간다. (위 스크린샷에선 확인해볼라고 임시로 0~20으로 지정함.)

만약 임시로 잡은 중간값이 정답이라면 이거보다 더 작은값도 정답일 확률이 있으므로 end값을 반으로 줄이고 실험. 

중간값이 정답이 아니라면 중간값보다는 더 커야 하므로 start를 중간값+1로 지정하고 계산. 

이런식으로 거꾸로 역추적하는 방식을 쓰는데 이게 parametric search 인 것 같다.

코드의 count 어쩌구는 문제 조건을 참조.

솔직히 꼼수 같다. 그래도 정답만 찾으면 그만이니..

import sys

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

# https://ggodong.tistory.com/90
# https://herong.tistory.com/entry/SWEA-3813-%EA%B7%B8%EB%9E%98%EB%8F%84-%EC%88%98%EB%AA%85%EC%9D%B4-%EC%A0%88%EB%B0%98%EC%9D%B4-%EB%90%98%EC%96%B4%EC%84%9C%EB%8A%94

def isAvailable(p):
    now = 1
    cont = 0
    for i in range(1,lenS+1):
        # print("i,now,cont,p,S[i]",i,now,cont,p,S[i])
        if S[i] <= p:
            cont += 1
        else:
            cont = 0
        if cont == K[now]:
            cont = 0
            now += 1
            if now > lenK:
                break
    return now > lenK

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    lenS,lenK = map(int, input().split())
    S = list(map(int, input().split()))
    K = list(map(int, input().split()))
    S.insert(0,0)
    K.insert(0, 0)
    print(S,K)

    s = min(S)
    e = max(S)
    while s<e:
        m = (s+e) // 2
        print("s,m,e",s,m,e)
        if (isAvailable(m)):
            e = m
        else:
            s = m + 1
    print(s)

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