[BOJ][Python]백준 1654 풀이

오랜만입니다. 한동안 거의 백준 문제에 손을 안대고 있었는데요. 이번 문제는 제가 제법 헤맸던 문제입니다.

 

문제링크: https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

이 문제는 이분탐색(Binary Search)라는 알고리즘을 사용해야 하는데요. 예전에 배운 이후로 안써서 아예 까먹고 있다보니 생각해내는데에 시간이 많이 걸렸습니다. 

 

이분탐색을 쓰지 않을 경우 이 문제를 푼다고 생각하면 어떻게 하실건가요? 저는 보통 문제를 풀 때 프로그래밍 없이 머리로 푼다면 어떻게 풀지 플로우차트를 미리 짜놓고 그걸 코드로 옮기는 편인데요. 문제를 보자마자 짰던 코드는 이겁니다.

import sys
ssr = sys.stdin.readline

def count_line(line_len):
    cnt = 0
    for i in line:
        cnt += i//line_len
    return cnt

k,n=map(int, ssr().split())
tmp=n
line=[int(ssr()) for _ in range(k)]
while 1:
    line_len = sum(line)//tmp
    cnt = count_line(line_len)
    if cnt < n:
        tmp+=1
        continue
    else:
        line_len = sum(line)//(tmp-1)
        while 1:
            cnt = count_line(line_len)
            if cnt<n:
                line_len-=1
                continue
            elif cnt == n:
                print(line_len)
                break
        break

간단하게 설명을 드리면 n개가 나오는 가장 작은 값을 찾아서 그 값을 1씩 줄여나가는 방식이었습니다. 생각해내고 코드를 짜는데는 거의 10분도 채 안걸렸던것 같은데요. 결과는 당연히 시간초과... 다른 방법을 찾아야 했습니다.

 

아무리 고민을 해도 시간초과를 벗어날 수 없어서 잠시 다른 문제를 풀던 찰나에 무슨 알고리즘으로 분류가 되어있는지 봤더니 이분탐색으로 되어있더군요. 그래서 이분탐색으로 도전해본 결과 풀 수 있었습니다.

 

정답 코드 :

import sys
ssr = sys.stdin.readline

k,n = map(int, ssr().split())
line = [int(ssr()) for _ in range(k)]
low = 1
high = sum(line) // n
while low <= high:
    value = (low + high) // 2
    cnt = 0
    for i in line:
        cnt += i // value
    if cnt < n:
        high = value - 1
    elif cnt >= n:
        low = value + 1

print(high)

이분 탐색은 중간값 정리와도 상당히 관련이 있는데요. 미지의 해가 어떤 범위 내에 존재할 때 그 범위를 좁혀가면서 해를 추측해나가는 방식입니다. 위의 문제에 적용해본다면 'n개를 만들 수 있는 최대한 큰 전선의 길이'가 해가 될 것입니다. 따라서 범위를 조절해서 제일 큰 값을 출력하면 맞는 값이 나오게 될 것입니다. 값이 정수로 한정된다는 것도 한몫하구요.

 

확실히 문제 풀이를 자주 안하다보니 이런 문제 푸는 스킬들이 점점 퇴화하는 것 같습니다. 도움이 되셨기를 바랍니다.