[백준]2805 나무 자르기 - 실버 2
[오늘의 문제]
https://www.acmicpc.net/problem/2805
[오늘의 학습 키워드]
- 이분 탐색, 구현
1. 문제설명
나무가 N개 주어지고 상근이가 필요로 하는 높이 M이 주어질 때
나무를 최소한으로 자르기 위해 절단기의 높이를 설정하려 합니다.
나무가 20 15 10 17이 주어진 경우 절단기의 높이를 15로 설정하면 나무는 15 15 10 15 로 잘리고 잘린 부분의 길이는 7로 상근이가 원하는 길이 7미터를 얻게 됩니다.
이때 절단기의 높이는 15로 최소한의 나무를 절단하기 위해 설정한 절단기의 높이를 출력하는 문제 입니다.
[제한사항]
- 시간 제한 1초
- 메모리 제한 256MB
- 1 ≤ N ≤ 1,000,000
- 1 ≤ M ≤ 2,000,000,000
- 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.
- 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.
2. 접근방식
절단기의 높이를 구하는 문제이니 이분 탐색을 이용해 문제를 해결할 수 있습니다.
절단기의 최소 높이와 최대 높이를 각각 구한후 절단기의 중가 높이를 설정해 줍니다.
이때 설정한 중간 높이로 나무를 잘라본 뒤 자르고 나온 나무 조각의 길이가 M이 될 때 까지 절단기의 최소 높이와 최대 높이를 변경해 가며 나무를 잘라보면 될 것 같습니다.
3. 코드
import sys
input = sys.stdin.readline
# 입력
N, M = map(int, input().split())
trees = list(map(int, input().split()))
# 절단기의 최소 높이, 최대 높이 구하기
start, end = 1, max(trees)
# 최소 높이와 최대 높이가 같아 질때까지만 반복
while (start <= end):
# 절단기의 중간 높이
mid = (start + end) // 2
# 구하려는 나무 토막의 길이
height = 0
for tree in trees:
# 나무가 절단기의 높이보다 작으면 음수값이 hieght에 더해져 값이 달라지기 때문에 해당 조건을 설정
if tree >= mid:
height += tree - mid
# 구하려는 길이보다 토막의 길이가 크면 최소 높이 변경
if height > M:
start = mid + 1
# 반대의 경우 최대 높이 변경
elif height < M:
end = mid - 1
# 같아진 경우 종료
else:
end = mid
break
print(end)[코드설명]
# 절단기의 최소 높이, 최대 높이 구하기
start, end = 1, max(trees)
# 최소 높이와 최대 높이가 같아 질때까지만 반복
while (start <= end):
# 절단기의 중간 높이
mid = (start + end) // 2
# 구하려는 나무 토막의 길이
height = 0
for tree in trees:
# 나무가 절단기의 높이보다 작으면 음수값이 hieght에 더해져 값이 달라지기 때문에 해당 조건을 설정
if tree >= mid:
height += tree - mid
입력받은 나무중 최소 높이와 최대 높이를 각각 구한후 중간 값으로 절단기의 높이를 설정합니다.
이때 나무를 잘라보는데 그 합을 구하기 위해 height 변수를 생성해 주었고, 전체 나무들 중 설정한 절단기 높이보다 높은 나무만 잘라줍니다.
이를 설정하지 않으면 height에 음수값이 들어가 결과가 달라집니다.
# 구하려는 길이보다 토막의 길이가 크면 최소 높이 변경
if height > M:
start = mid + 1
# 반대의 경우 최대 높이 변경
elif height < M:
end = mid - 1
# 같아진 경우 종료
else:
end = mid
break
print(end)
이때 나무토막의 길이가 구하려는 길이보다 길다면 절단기의 높이를 높여 전체 나무토막의 길이를 줄여줘야 합니다.
따라서 start 값을 mid + 1로 변경해주고
전체 나무토막의 길이가 구하려는 나무토막의 길이보다 짧다면 절단기의 높이를 낮춰 전체 나무토막의 길이를 늘려줘야 합니다.
따라서 end 값을 mid - 1로 변경해줍니다.
같아진 경우 end 를 mid로 변경하고 while문을 종료시킨 뒤 출력해줍니다.
4. 결과
[회고]
사실 문제자체는 크게 어렵지 않았는데 시간이 오래걸려 최적화를 고민한 문제 입니다.
처음 시도했을때 시간이 4868ms으로 오래 걸려서 시간을 줄이려고 readline을 시도해보고, 다른 방법을 시도했는데 오히려 시간초과가 발생했습니다.
도저히 방법이 떠오르지 않아 다른분의 코드를 참고했는데 그분은
from collections import Counter 를 사용하였습니다.
이게 어떤 코드인지 찾아보니 다음과 같았습니다.
이 방식은 중복된 데이터의 갯수를 세어주는 함수였습니다.
이를 활용하면 중복된 나무의 높이를 쉽게 계산하기 때문에 불필요한 for 반복문을 없앨 수 있었고 이는 최대 1,000,000 개 주어지는 나무의 높이를 일일이 비교하며 잘라서 확인할 필요가 사라지는 코드 였습니다.
import sys
from collections import Counter
# 입력
n, m = map(int, sys.stdin.readline().split())
trees = Counter(map(int, sys.stdin.read().split()))
# 초기 설정
s = 1
e = 1000000000
while s <= e:
mid = (s + e) // 2 # 중간값 설정
# 중간값을 기준으로 잘랐을 때 가져갈 수 있는 나무 길이 합 계산
tot = sum((h - mid) * i for h, i in trees.items() if h > mid)
if tot >= m: # 가져갈 수 있는 나무 길이 합이 목표보다 크거나 같은 경우
s = mid + 1 # 높이를 높여야 함
elif tot < m: # 가져갈 수 있는 나무 길이 합이 목표보다 작은 경우
e = mid - 1 # 높이를 낮춰야 함
print(e) # 결과 출력
해당 코드가 시간 최적화를 위해 확인해본 코드 였습니다.
저는 Counter 모듈의 여부를 몰라서 시도하지 않았지만 코드를 해석해보면 이런 의미입니다.
trees를 Counter를 통해 받기 때문에 trees는
trees = Counter({20:1, 15:1, 10:1, 17:1})
이런 형식으로 생성 됩니다.
중복이 있으면 새로운 높이가 더해지는게 아닌 갯수가 올라가는 형식입니다.
파이썬의 딕셔너리와 비슷한 형태입니다.
최소 높이를 1, 최대 높이를 나무의 최대 높이로 설정한 뒤 중간 값을 구합니다.
이때 중간값은
tot = sum((h - mid) * i for h, i in trees.items() if h > mid)
이 코드로 구하게 되는데 이 코드는 반복문을 통해 나무의 높이와 개수를 구합니다.
나무의 높이는 h, 개수는 i로 구해준 뒤 h에서 mid 값을 빼주는데 이때 빼주는 조건은 mid보다 큰 경우만 빼줍니다.
그 후 그 개수 i를 곱한뒤 그 총 합을 sum 해서 전체 필요한 나무 토막의 길이를 구하게 됩니다.
Counter 없이 한다면 매 리스트를 순회하며 일일이 높이마다 구해주어 하는 과정을 없애 주었으니 시간이 훨씬 단축되는 것입니다.
애초에 Counter를 통해 생성하면 중복 나무의 높이는 갯수가 올라가는 형식으로 변경되니 리스트의 길이도 변경되어 탐색의 시간이 줄어드는 것입니다.
이번 시간에 Counter 모듈을 배웠고 사용법도 알게 되었습니다.