백준 1508 레이스

문제

https://www.acmicpc.net/problem/1781

풀이

심판을 k개의 미리 정해진 위치중 m명의 심판을 배치해야 한다.
배치되는 최대의 경우의 수를 계산해보면, 50C25라고 가정했을때, 126410606437752번의 연산이 필요함으로 모든 경우의 수를 따져보는 접근방식은 올바르지 않다.

이러한 문제는 결정문제를 해결하는 방식으로 접근하면 좋다.
미리 답을 내놓고 그것이 올바른지 결정하는 접근 방식이다.
심판과 심판의 사이의 최소거리가 x라고 결정되어 있다면, m명의 심판을 배치할 수 있을까? 만약 배치할 수 있다면 x보다 큰 값들 중에 위의 조건을 만족하는 값은 무엇인지 찾아야 하고, 배치할 수 없다면 x보다 작은 값들 중에 위의 조건을 만족하는 값을 찾아야 한다.

가능한 심판 사이의 거리의 최소부터 최대까지 사이에 조건이 바뀌는 지점이 한 지점 존재할 것이다. 그 지점을 찾기 위해 이분탐색을 하면 된다.

결정문제 이분탐색에 대해 이해하는 데 아래의 글이 많은 도움이 됬다.

https://www.acmicpc.net/blog/view/109

n,m,k = list(map(int,input().split()))
arr = list(map(int,input().split()))
def check(x): ## 심판과 심판 사이의 거리가 x보다 크게 배치할 때 m명을 배치할 수 있을지 검증
    cnt = 0; pos = -1
    for i in range(k):
        if pos <= arr[i]:
            cnt += 1
            pos = arr[i] + x
    if cnt < m: return False
    else: return True

def search():
    start = 0; end = arr[-1]+1
    while start + 1 < end:
        mid = (start + end) // 2
        if check(mid): start = mid
        else: end = mid
    return start

def go():
    ans = ''
    pos = -1; cnt = 0
    for i in range(k):
        if pos <= arr[i] and cnt < m:
            ans += '1'
            pos = arr[i] + dist
            cnt += 1
        else:
            ans += '0'
    print(ans)
dist = search()
go()

boj 카테고리 내 다른 글 보러가기