[백준 - Python] 1654. 랜선 자르기

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

1654번: 랜선 자르기

 

코드

k, n = map(int, input().split())
lan = []
for _ in range(k):
    lan.append(int(input()))

start, end = 1, max(lan)
while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for l in lan:
        cnt += l//mid

    if cnt >= n: # 랜선 길이를 늘려야 함
        start = mid + 1
    else:
        end = mid - 1

print(end)

 

 

 

 

 

시간 복잡도

처음에 떠올린 풀이는

가지고 있는 랜선들 중, 가장 작은 랜선의 길이를 초기 값으로 설정하고

해당 초기 값에서 1씩 줄여나가면서

그 값으로 주어진 랜선들을 전부 나눠보며 나온 몫을 더해서

만들어야 하는 랜선의 개수를 만족하면

그 값을 정답으로 출력하면 되지 않을까 하는 생각이었다.

 

문제에서 랜선의 길이는 2의 31승 - 1보다 작거나 같은 자연수라는 조건이 주어져 있다.

2의 31승은 대략 21억에 가까운 수이다.

가장 작은 랜선의 길이가 십억이 넘어가는 수일 수 있고,

게다가 주어진 랜선들을 전부 나눠보면서 몫을 구하고

그 몫들을 전부 더하는 과정을 거쳐야 하는데

랜선의 개수인 N은 백만 이하의 정수로 주어진다는 범위 조건이 있다.

 

위의 내용들을 토대로,

내가 처음 떠올린 풀이의 시간 복잡도를 생각해본다면,

십억은 훌쩍 넘는, 즉 2초 안에 계산이 불가한 시간 복잡도를 갖게 되기 때문에

해당 문제는 그런 방식으로 풀어낼 수 없다는 판단이 내려진다.

 

이진 탐색으로 탐색을 하는 풀이의 시간 복잡도를 생각해보면,

log10,000(이진 탐색 : log(K 범위 최댓값)) * 1,000,000(몫 구하는 반복문에서 N 범위 최댓값)

= 4,000,000 (4백만) 의 시간 복잡도를 갖는다.

 

이진 탐색 풀이는, 문제에서 주어진 시간 제한을 넘지 않음을 확인할 수 있다.

따라서, 해당 문제는 이진 탐색 방식으로 해결이 가능하다.

 

 

아이디어

이진 탐색을 떠올리고 활용할 줄 안다면,

문제 해결을 위한 특별한 아이디어는 없다.

 

시작 인덱스를 1, 끝 인덱스를 랜선의 최댓값으로 설정하고

이를 초기값으로 이진 탐색을 시작한다

 

mid 값을 N개를 만들 수 있는 랜선의 최대 길이라고 가정하고

필요한 연산을 수행해서

N개와 현재 mid 값으로 계산한 총 랜선의 개수를 비교해

시작 인덱스 혹은 끝 인덱스를 조정하는 과정을 거치면 된다.

 

 

코드 설명

입력을 받고 시작 인덱스와 끝 인덱스의 초기 설정값을 지정해준다.

두 인덱스가 교차하지 않을 때까지, mid를 갱신한다

 

주어진 모든 랜선들에 대해 몫 계산을 수행하고,

cnt 변수에 그 계수를 누적 합산 해준다.

 

계산이 끝난 후,

cnt 값이 N보다 크다면, 랜선의 길이가 해답 길이보다 짧아서 랜선 개수가 많아진 것이므로

시작 인덱스를  mid + 1 값으로 갱신해서 랜선 길이를 늘리고

cnt 값이 N보다 작다면, 랜선의 길이가 해답 길이보다 길어서 랜선의 개수가 적어진 것이므로

끝 인덱스를 mid - 1 값으로 갱신해서 랜선 길이를 줄인다

 

if cnt  == n을 따로 분기로 빼지 않는 이유는

cnt = n인 경우가 여러 경우가 있을 수 있기 때문이다

 

그 여러 경우 중 최대값을 구하기 위해서

마지막에 print(end)를 해준다