[김태원 알고리즘] 마구간 정하기 (결정 알고리즘)

사용 언어: Python3

문제

풀이

내 풀이

# 가장 가까운 두 말 사이 거리 반환
def calc(isExist):
    ret = 10000
    stack = [] # isExist에서 False인 원소의 인덱스를 담아둘 스택
    for i in range(len(isExist)):
        if isExist[i]:
            stack.append(i)
        if len(stack) == 2:
            ret = min(ret, lst[stack[1]] - lst[stack[0]])
            stack.pop(0) # 맨 앞 원소 pop
    return ret

from itertools import combinations

N, C = map(int, input().split())
lst = [int(input()) for _ in range(N)]
lst.sort()

res = -1
for x in combinations(lst[1:-1], C-2):
    isExist = [False] * N
    isExist[0], isExist[-1] = True, True
    for val in x:
        isExist[lst.index(val)] = True
    res = max(res, calc(isExist))
print(res)

• 성공

내 풀이 - 2

N, C = map(int, input().split())
lst = [int(input()) for _ in range(N)]
lst.sort()

src, dest = 1, lst[-1] # src, dest: 가장 가까운 두 말의 거리의 최대 최소
res = -1
while src <= dest:
    mid = (src+dest) // 2 # 모든 말들 사이의 거리는 mid보다 크거나 같아야 한다
    pos = lst[0] # 바로 이전 말의 위치 # 첫번째 말은 마구간 처음에 위치
    cnt = 1 # 말의 수
    for i in range(1,N): # 첫번째 말 제외하고 각 구간마다 말 놓아보기
        if lst[i]-pos >= mid:
            pos = lst[i] # 두번째 말 놓기
            cnt += 1
    if cnt == C:
        res = max(res, mid)
    if cnt < C: # 거리가 너무 멀어서 C마리보다 적게 배치한 것
        dest = mid-1 # 거리 줄이기
    else: # 🌟 등호는 여기 포함!
        src = mid+1
print(res)

다른 풀이

# ✅ 최소 간격이 mid일 때 몇 마리의 말을 배치할 수 있는지 반환
def calc(mid):
    cnt = 1
    pos = lst[0] # 마지막에 배치한 말의 위치
    for i in range(1,N):
        if lst[i] - pos >= mid: # 다음말 배치 가능
            cnt += 1
            pos = lst[i]
    return cnt

N, C = map(int, input().split())
lst = [int(input()) for _ in range(N)]
lst.sort()

src, dest = 1, lst[-1] # ✅ src, dest: 가장 가까운 두 말의 거리의 최대 최소
res = -1
while src <= dest:
    mid = (src+dest) // 2 # ✅ 모든 말들 사이의 거리는 mid보다 크거나 같아야 한다
    if calc(mid) >= C: # ✅ 등호 포함
        res = max(res, mid)
        src = mid+1 # 이제 더 큰 mid를 찾아야하니까 작은 범위 날리기
    else: # 답을 못 찾았으면 mid를 줄여야 함
        dest = mid-1 # 큰 범위 날리기

print(res)

• calc() 함수를 정의해 더 깔끔하게 푼 풀이이다.
• 등호를 주의하자!

내 풀이 - 0421 추가

def calc(mid):
    tmp = lst[0] # 이전 말의 위치
    cnt = 1 # 첫번째 마구간에 말 한마리 배치 (말의 수)
    for i in range(1,N):
        if lst[i] - tmp >= mid:
            tmp = lst[i]
            cnt += 1
    return cnt

N, C = map(int, input().split())
lst = [int(input()) for _ in range(N)]
lst.sort()

src, dest = 1, lst[-1]
res=-1
while src<=dest:
    mid = (src+dest)//2 # 두 말 사이 거리
    cnt = calc(mid) # 말 사이 거리가 mid 일 때 말 몇마리 들어가는지
    if cnt>=C:
        res = max(res, mid)
        src = mid+1
    else:
        dest = mid-1
print(res)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기