[백준 / python] 1654번 랜선 자르기

오늘은 이분 탐색 유형인 백준 1654번 문제, 랜선 자르기를 풀어보겠습니다!

 

< 문제 확인 >

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

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

주요 내용은 K개의 랜선을 잘라서 N개의 같은 길이의 랜선을 만들면서 그 길이의 최대값을

구하는 것입니다. 이를 위해, 이분 탐색을 활용하여 가능한 최대 길이를 효율적으로 찾아냅니다.

 

(모든 랜선은 정수 길이로 잘라야 하며, 랜선의 길이를 최대화)

 

즉, 랜선의 최소 길이인 1부터 최대 길이 까지의 중간 값을 탐색하면서,

중간 값으로 잘라 N개의 랜선을 만들 수 있는지 확인합니다.

이후 더 긴 길이로도 가능한지 확인하고, 불가능하면 길이를 줄여 나가면서 최대 길이를 찾아냅니다!

 

✔️ 가능한 시간복잡도

K는 최대 10,000, N은 최대 1,000,000이고,

이분 탐색을 사용하면 O(K*log(최대길이))로 해결할 수 있습니다.

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N을 입력받습니다.

2. 이분 탐색을 위해 최대/최소 랜선 길이를 설정합니다.

3. 중간 길이를 구하고, 해당 길이로 랜선을 잘라 N개 이상의 랜선을 만들 수 있는지 확인합니다.

4. 가능하다면 길이를 늘려가며 탐색하고, 불가능하면 길이를 줄여 나갑니다.

5. 최종적으로 가능한 최대 길이를 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

무문 별하게 “맞았습니다”가 나올 때까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

---

📌 정답 코드

import sys
input = sys.stdin.read
data = input().split()

K = int(data[0])
N = int(data[1])
lan_line = [int(data[i]) for i in range(2, 2 + K)]

# 이분 탐색을 위한 랜선 초기 설정
start, end = 1, max(lan_line)
result = 0

while (start <= end):
    mid = (start + end) // 2
    
    # 중간 길이로 잘라서 만들 수 있는 랜선의 개수 계산
    count = 0
    for lan in lan_line:
        count += lan // mid
    
    # N개 이상의 랜선을 만들 수 있는 경우, 길이를 늘려서 탐색
    if (count >= N):
        result = mid
        start = mid + 1
    # 불가능한 경우, 길이를 줄여서 탐색
    else:
        end = mid - 1

print(result)

 

최근에 풀어본 이분 탐색 문제 중 가장 생각할 부분이 많았지만

개념 중심으로 차근차근 생각해보며 해결할 수 있었습니다!

어느덧 중반을 넘어선 코테 챌린지 매일매일 힘내서 풀어볼게요~😃

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no