[#1654] 부분수열의 합

❓ Question

📖 Before Start

이 친구도 완전 탐색 으로 풀면 되겠네! 라는 안일한 생각을 가졌습니다.

요새 브루트 포스 문제를 많이 풀다보니, 일단 뭐든지 완전 탐색으로 풀어보자는 마인드가 생겼다.
이번 문제도 존재하는 모든 경우의 수를 탐색해보자는 결론이 나왔고, 아래와 같이 설계를 시작했다.

✒️ Design Algorithm

이번 문제도 무조건 순차 탐색 (Linear Search) 일거라 생각했는... 데? 어라?

길이가 각각 다른 랜선이 있고, 이를 모두 일정한 길이로 잘랐을 때 몇 개의 랜선이 나오느냐?
결국 짧게 자르면 더 많은 수량의 랜선이 나오니, 길이와 수량을 잘 체크하여 탐색을 진행하였다.

아래는 필자가 문제를 풀기 전 작성한 알고리즘 설계이다.

K개의 랜선을 잘라 N개의 랜선을 만들어야 한다. 수량은 N개 이상도 가능하다.
현재 K개의 랜선을 보유 중이나, 길이가 각각 달라 이를 동일하게 잘라야 한다.

1. 첫 번째 줄에는 K, N 이 공백을 기준으로 연달아 입력된다.
2. 그 후 K개의 랜선에 대한 길이 가 각각 K개만큼 입력된다.

• 자를 길이를 임의로 설정한 후, 각각의 랜선을 잘랐을 때 나오는 수량을 구한다.
• 잘라서 나온 랜선의 수량을 모두 더한 값이 N보다 같거나 큰 지를 구한다.
• 그 중 가장 잘랐을 때 길이가 긴 케이스를 추출하여 구한다.

💻 Making Own Code

❌ Wrong Code

import sys

k, n = map(int, sys.stdin.readline().split())
data = [int(sys.stdin.readline()) for _ in range(k)]
max_length = 1

for length in range(1, min(data)+1):
    count = 0
    for line in data:
        count += line // length
    if count >= n:
        if length > max_length:
            max_length = length
    else:
        break
        
print(max_length)

하지만 이 코드는 계속해서 시간 초과 를 내뿜으며 장렬히 산화하였다.

PyPy3 으로 제출해도 상단의 코드는 계속해서 시간 초과를 내뿜으며 돌아가라는 말을 남겼다.
하지만 순차적으로 값을 탐색해나가는 게 아니면 대체 어떻게 값을 탐지할 수 있단 말인가?
그렇게 한참을 헤맨 끝에 찾은 결론은, 바로 이진 탐색 을 활용하여 푸는 방식이었다.

✅ Correct Code

import sys

k, n = map(int, sys.stdin.readline().split())
data = [int(sys.stdin.readline()) for _ in range(k)]
min_len, max_len = 1, max(data)

while min_len <= max_len:
    mid_len, count = (min_len + max_len) // 2, 0
    for line in data:
        count += line
    if count >= n:
        min_len = mid_len + 1
    else:
        max_len = mid_len - 1

print(max_len)

이진 탐색 이라는 개념을 처음 알았지만, 시간 복잡도가 정말 많이 줄어드는 건 부정하기 힘들다.
위에서 쓴 순차 탐색은 시간 복잡도가 O(n) 에 비해, 이진 탐색은 무려 O(logN) 이라고 한다.

중간 값을 기준으로 점점 절반 씩 탐색 영역을 좁혀나가는 방식이라니.. 이건 너무 사기지 않는가?
여러분들은 필자의 경우처럼 실수하는 일 없이, 잘 풀이하여 문제를 해결하기 바란다.