[python] 백준 1508 레이스

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

1508번: 레이스

 

문제 해결

• combination으로 모든 경우의 수를 체크하려 했지만 $ 50 \choose 25$ 와 같이 경우의 수가 큰 경우는 시간초과 난다.
• 경우의 수가 생각이 안나서 인터넷에서 다른 사람들의 풀이를 참고하였다.
• 이진탐색으로 가장 짧은 길이의 최대 길이를 만들어서 정답을 구할 수 있었다.
• 가장 짧은 길이를 start(=0), 가장 길 수 있는 길이를 end-1로 놓고 시작한다.
• 왜 end를 가장 긴 길이로 안하냐면 start<=end가 되어야하는데 반복문이 안 끝날 수 있다.

 

CODE

import sys


n, m, k = map(int, input().split()) # n:길이, m:심판 수, k: 정해진 위치 (m<=k)
position = list(map(int, input().split()))

def check(x):
    now = -1
    cnt = 0
    for i in range(k):
        if now <= position[i]:
            cnt += 1
            now = position[i] + x
    if cnt <m:
        return False
    return True
start = 0
end = position[-1] + 1
while start+1 <end:
    mid = (start+end)//2
    if check(mid):  # 길이(mid=심판사이가장 작은 거리)가 적당하거나 작다
        start = mid # 키워야 하니 start= mid
    else: # 길이(mid=심판사이 가장 작은 거리)가 너무 크다
        end = mid # 줄여야하니 end = mid
ans = ''
now = 0
cnt = 0
for i in range(k):
    if now <= position[i] and cnt<m:
        ans += '1'
        now = position[i] + start
        cnt += 1
    else:
        ans +='0'
print(ans)