파이썬 알고리즘 270번 | [백준 1477번] 휴게소 - 이분탐색

270. 휴게소

1) 어떤 전략(알고리즘)으로 해결?

• 이분탐색

2) 코딩 설명

<내 풀이>

< 내 틀렸던 풀이, 문제점>

import sys

# 현재 휴게소의 개수 N, 
# 더 지으려고 하는 휴게소의 개수 M, 
# 고속도로의 길이 L
n,m,l = map(int, sys.stdin.readline().split())
location = list(map(int, sys.stdin.readline().split()))

maxlen, maxstart, maxend = -1,-1,-1
for _ in range(m) : 
    for i in range(len(location)-1) : 
        if location[i+1]-location[i] > maxlen : 
            maxlen = location[i+1]-location[i]
            maxstart = location[i]
            maxend = location[i+1]
    print(maxlen, maxstart, maxend, "iiiiiiiiiiiiiii")
    while maxstart<=l and maxend<=l and maxstart<maxend : 
        mid = (maxstart+maxend)//2 
        print(maxstart, maxend, (maxstart+maxend)//2 , "maxlen : ", maxlen)
        if (mid-maxstart) > (maxend-mid) and (mid-maxstart < maxlen) : 
                print("첫 케이스")
                maxlen = mid-maxstart
                maxend = mid
        elif (mid-maxstart)<=(maxend-mid) and (maxend-mid < maxlen) : 
                print("두 케이스")
                maxlen = (maxend-mid)
                maxstart = mid

    location.append(mid)

for i in range(len(location)-1) : 
        if location[i+1]-location[i] > maxlen : 
            maxlen = location[i+1]-location[i]
            maxstart = location[i]
            maxend = location[i+1]

print(maxlen)

흐으음

import sys
# 현재 휴게소의 개수 N, 
# 더 지으려고 하는 휴게소의 개수 M, 
# 고속도로의 길이 L
n,m,l = map(int, sys.stdin.readline().split())

location = list(map(int, sys.stdin.readline().split()))
location.append(0)
location.sort()
maxlen, maxstart, maxend = -1,-1,-1

for i in range(len(location)-1) : 
        if location[i+1]-location[i] > maxlen : 
            maxlen = location[i+1]-location[i]
            maxstart = location[i]
            maxend = location[i+1]

for _ in range(m) : 
    cont=True
    while maxstart<l and maxend<l and maxstart<= maxend and cont : 
        mid = (maxstart+maxend)//2 
        # print("start : ", maxstart, "/end : " , maxend, "/mid : " , (maxstart+maxend)//2 , "/maxlen : ", maxlen, "/location : ", location)

        if (mid-maxstart) > (maxend-mid) and (mid-maxstart < maxlen) : 
                # print("첫 케이스")
                maxlen = mid-maxstart
                maxend = mid-1
        elif (mid-maxstart)<=(maxend-mid) and (maxend-mid < maxlen) : 
                # print("두 케이스")
                maxlen = (maxend-mid)
                maxstart = mid+1
        cont=False

    location.append(mid)
    location.sort()

    for i in range(len(location)-1) : 
        if location[i+1]-location[i] > maxlen : 
            maxlen = location[i+1]-location[i]
            maxstart = location[i]
            maxend = location[i+1]

for i in range(len(location)-1) : 
        if location[i+1]-location[i] > maxlen : 
            maxlen = location[i+1]-location[i]
            maxstart = location[i]
            maxend = location[i+1]
# print("최종    start : ", maxstart, "/end : " , maxend, "/mid : " , (maxstart+maxend)//2 , "/maxlen : ", maxlen, "/location : ", location)
print(maxlen)

예제

6 7 800
622 411 201 555 755 82

위 예제 넣었을 때 최솟값 답이 70인데 나는 72가 나오는 상황
어디서 얘가 잘못되는거지

import sys
# 현재 휴게소의 개수 N, 
# 더 지으려고 하는 휴게소의 개수 M, 
# 고속도로의 길이 L
n,m,l = map(int, sys.stdin.readline().split())

location = list(map(int, sys.stdin.readline().split()))
location.append(0)
location.sort()
maxlen, maxstart, maxend = -1,-1,-1

for i in range(len(location)-1) : 
        if location[i+1]-location[i] > maxlen : 
            maxlen = location[i+1]-location[i]
            maxstart = location[i]
            maxend = location[i+1]

for _ in range(m) : 
    cont=True
    while maxstart<=l and maxend<=l and maxstart< maxend and cont : 
        mid = (maxstart+maxend)//2
        print("start : ", maxstart, "/end : " , maxend, "/mid : " , (maxstart+maxend)//2 , "/maxlen : ", maxlen, "/location : ", location)

        if (mid-maxstart) > (maxend-mid) and (mid-maxstart < maxlen) : 
                # print("첫 케이스")
                maxlen = mid-maxstart
                maxend = mid-1

        elif (mid-maxstart)<=(maxend-mid) and (maxend-mid < maxlen) : 
                # print("두 케이스")
                maxlen = (maxend-mid)
                maxstart = mid+1
        cont=False

    location.append(mid)
    location.sort()

    for i in range(len(location)-1) : 
        if location[i+1]-location[i] > maxlen : 
            maxlen = location[i+1]-location[i]
            maxstart = location[i]
            maxend = location[i+1]

for i in range(len(location)-1) : 
        if location[i+1]-location[i] > maxlen : 
            maxlen = location[i+1]-location[i]
            maxstart = location[i]
            maxend = location[i+1]

print("최종    start : ", maxstart, "/end : " , maxend, "/mid : " , (maxstart+maxend)//2 , "/maxlen : ", maxlen, "/location : ", location)
print(maxlen)

---

ZERO DIVISION ERROR

import sys
# 현재 휴게소의 개수 N, 
# 더 지으려고 하는 휴게소의 개수 M, 
# 고속도로의 길이 L
n,m,L = map(int, sys.stdin.readline().split())

location = list(map(int, sys.stdin.readline().split()))
location.append(0) # 0과 
location.append(L) # 맨 끝 점 추가해줘야 함, 여기에는 휴게소 세워질 수 없으므로 
location.sort() # 정렬

r = L+1
l = 0

while l<r:
    mid=(r+l)//2 # 최대거리 후보
    cnt = 0 # mid 간격으로 휴게소 추가 설치했을 때 총 휴게수 갯수
    for i in range(1,n+2): # n에다가 내가 0이랑 맨 끝 위치 추가
        # mid 를 최댓값으로 잡고 
        cnt+= (location[i]-location[i-1]-1)//mid # 현재 휴게소들 사이에 mid 간격
    if cnt<=m : # mid 만큼 잡아서 충분히 휴게소 만들 수 있음, 그럼 mid 간격 줄이기
        r=mid
    else : # mid 만큼 잡아서 휴게소 설치하면 모자라더라
        l=mid+1 # mid를 넓히자,,
        
print(l)

<반성 점>

<배운 점>

• 들어오는 문자 리스트를 모두 정수로 바꿔버리기

mapp = 
list(list(map(int,sys.stdin.readline().rstrip())) for _ in range(n))

초기

['1', '1', '1', '1', '0', '0', '0', '0']
['1', '1', '1', '1', '0', '0', '0', '0']
['0', '0', '0', '1', '1', '1', '0', '0']
['0', '0', '0', '1', '1', '1', '0', '0']
['1', '1', '1', '1', '0', '0', '0', '0']
['1', '1', '1', '1', '0', '0', '0', '0']
['1', '1', '1', '1', '0', '0', '1', '1']
['1', '1', '1', '1', '0', '0', '1', '1']

위 코드 적용 후

[1, 1, 1, 1, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 1, 1]
[1, 1, 1, 1, 0, 0, 1, 1]