[백준] 1654 랜선 자르기 - 실버 2

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• 구현, 이분 탐색

---

1. 문제설명

 

K개의 랜선이 주어질 때 주어진 랜선을 이용해 N개의 랜선을 만들때 만들 수 있는 가장 긴 랜선의 길이를 찾는 문제 입니다.

 

즉 N개의 랜선을 만들때 최대한 긴 랜선을 만들어야 하는데 이런 문제는 이분 탐색을 이용하면 쉽게 해결할 수 있습니다.

---

[제한사항]

• 시간 제한 2초
• 메모리 제한 128MB
• K는 1이상 10,000이하의 정수
• N은 1이상 1,000,000이하의 정수
• K ≦ N

---

2. 접근방식

이 문제는 이분 탐색을 이용하면 해결할 수 있습니다.

 

가장 짧은 랜선의 길이는 1이고 주어진 랜선 중 가장 긴 길이를 가진 랜선을 max(LAN) 을 통해 구하게 되었을 때

 

중간값을 구하고 그 길이를 토대로 N개의 랜선을 구해줍니다.

 

이때 이 값으로 만든 랜선이 N개 이상이라면 start를 늘려서 랜선의 길이를 늘려주고

 

N개 미만 이라면 랜선의 길이를 줄여 갯수를 맞춰주어야 합니다.

 

이를 그대로 코드로 구현해 보겠습니다.

---

3. 코드

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
LAN = [int(input().strip()) for _ in range(K)]

# 가장 짧은 랜선, 가장 긴 랜선
start, end = 1, max(LAN)
while (start <= end):

    # 중간값 구하고 N과 비교하기 위한 count
    mid = (start + end) // 2
    count = 0

    # 입력 받은 LAN을 현재 중간 값으로 나누면 랜선의 갯수가 나옴
    for L in LAN:
        count += L // mid
    
    # 이때의 count 갯수가 N개 이상이라면 랜선의 길이 늘리기
    if count >= N:
        start = mid + 1
    
    # 아니라면 랜선의 길이 줄이기
    else:
        end = mid - 1
print(end)

---

[코드설명]

코드의 동작을 이해하기 쉽게 pythontutor를 활용해 설명해 보겠습니다.

 

우선 이분 탐색을 활용하기 위해 주어진 랜선중 가장 길이가 짧은 1과, 가장 길이가 긴 max(LAN)을 통해 시작 지점과 종료 지점을 설정해 줍니다.

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
LAN = [int(input().strip()) for _ in range(K)]

# 가장 짧은 랜선, 가장 긴 랜선
start, end = 1, max(LAN)

 

그리고 while 문을 이용해 start 지점과 end 지점이 같아지는 순간까지 반복을 실시해 줍니다.

 

입력이 주어질 때 가장 길이가 긴 LAN은 802 입니다.

이 값을 이용해 중간값을 구하면 1 + 802 // 2 이므로 중간값은 401이 되겠죠

 

이 401이 우리가 구하려는 랜선의 길이 입니다.

 

401의 길이를 가진 랜선을 통해 현재의 랜선들을 잘라줍니다.

이는 LAN 배열에 입력된 랜선들을 하나씩 꺼내와 401의 길이로 나눈 값을 count에 더해주면 되겠죠

 

모든 반복을 실시했을때 count는 다음과 같습니다.

 

401 길이의 랜선으로는 최대 5개 까지밖에 랜선을 만들수 있습니다.

 

우리가 구하려는 랜선의 갯수가 N보다 모자라니 랜선의 길이를 줄여줘야 겠죠 그럼 end값을 mid 값으로 바꿔주는 겁니다.

 

이때 end 값은 mid의 401을 그대로 가져가는게 아닌 401 에서 1을 빼준 값으로 설정해야 제대로 된 이분 탐색을 실시할 수 있습니다.

 

---

while (start <= end):

    # 중간값 구하고 N과 비교하기 위한 count
    mid = (start + end) // 2
    count = 0

    # 입력 받은 LAN을 현재 중간 값으로 나누면 랜선의 갯수가 나옴
    for L in LAN:
        count += L // mid
    
    # 이때의 count 갯수가 N개 이상이라면 랜선의 길이 늘리기
    if count >= N:
        start = mid + 1
    
    # 아니라면 랜선의 길이 줄이기
    else:
        end = mid - 1
print(end)

 

이 과정을 반복하면 start와 end가 점점 가운데로 움직이며 원하는 랜선의 길이를 이용해 N개의 랜선을 구할 수 있습니다.

 

이때 최대 랜선의 길이를 출력해야 하니 end를 출력해 주었습니다.

---

4. 결과

---

[회고]

처음 문제 설명을 봤을 때는 조금 헷갈렸습니다.

 

이분 탐색 문제인 것은 문제의 알고리즘 분류를 통해 알고 있었는데 오랜만에 이분 탐색 문제를 푸려고 하니 어떻게 했었지 하며 헷갈렸습니다.

 

문제를 다시 읽어보며 천천히 생각을 해보니 결국 구하고자 하는 것은 N개의 랜선을 만들때 최대 랜선의 길이 였습니다.

 

그 말은 주어진 랜선들을 이용해 N개의 랜선을 만들어야 한다는 소리 입니다.

 

그러기 위해선 주어진 랜선중 가장 큰 길이를 가진 랜선을 절반씩 잘라가면서 N개가 되었을 때 탐색 지점을 변경하면 될 것 같았습니다.

 

이 생각이 든 후 그대로 코드로 작성하였고 쉽게 문제를 해결할 수 있었습니다.

 

문제의 조건에 최소 1의 길이와 최대 10,000 길이의 랜선이 주어 지더라도 이분 탐색을 이용해 절반씩 탐색 범위를 설정한다면 2초 내에 모든 조건을 탐색이 가능하였습니다.