반응형
문제유형
이분 탐색
풀이 방법 도출 과정
1. 이 문제는 단순한 구현 문제처럼 보일 수 있지만, 이를 구현하는 방식에 따라 시간 복잡도가 커질 수 있다.
2. 따라서, 문제를 해결할 수 있는 더 효율적인 방법을 찾아야 한다. 이를 위해 이분 탐색을 활용하는 방식으로 접근하려 한다.
3. 이분 탐색을 적용하기 위해, 첫 번째로 left를 1로 설정하고, right는 주어진 랜선들의 길이 중에서 가장 긴 값으로 설정한다. 이렇게 설정하는 이유는 랜선 길이가 1부터 가장 긴 값까지 범위 안에 존재하기 때문이다.
3. 그 다음, 중간값인 mid를 계산한다. 그리고 mid 길이로 랜선을 나누었을 때, 얻을 수 있는 랜선의 개수가 주어진 N개 이상이 되는지 확인한다. 이 조건을 만족하는지 여부에 따라 이분 탐색을 반복하여 최적의 값을 찾는다.
시간 복잡도
입력 받기 O(K)
이분 탐색 log(max(lan))
각 반복에서의 연산 O(K)
다 합해서 O(K * log(max(lan)))이다.
코드 및 간단설명
이분탐색을 사용하여 문제를 풀었다.
def binary_search(lan, N):
left, right = 1, max(lan)
while left <= right:
mid = (left + right) // 2
lines = 0
for i in lan:
lines += i // mid
if lines >= N:
left = mid + 1
else:
right = mid - 1
return right
# 입력 받기
K, N = map(int, input().split())
lan = [int(input()) for _ in range(K)]
# 이분 탐색 함수 호출 및 결과 출력
print(binary_search(lan, N))
반응형
'Coding Test (코딩 테스트)' 카테고리의 다른 글
[class2]백준 1874번(스택 수열) - 코딩테스트 23일차(2025.02.13) (0) | 2025.02.13 |
---|---|
[class2]백준 1920번(수 찾기) - 코딩테스트 22일차(2025.02.12) (0) | 2025.02.12 |
코딩테스트 21일차(2025.02.11) - 백준2108번(통계학) (0) | 2025.02.11 |
코딩테스트 20일차(2025.02.09) - 백준2839번(설탕 배달) (0) | 2025.02.09 |
코딩테스트 19일차(2025.02.06) - 백준4949번(균형잡힌 세상) (0) | 2025.02.07 |