백준 2805 파이썬 풀이

안녕하세요 호박감자입니다.

블로그 글을 올리는게 쉽지 않네요. 하지만 놀고만 있느라 글을 못쓰고 있는건 아닙니다 ㅎㅎ

오늘부터는 알고리즘 스터디에서 공부하며 풀고있는, 백준 문제들에 대한 제 코드와 또 굉장히 좋다고 생각하는 다른 사람의 코드를 리뷰해보도록 하겠습니다.

특히나 이번 글은 제가 풀었던 방법을 먼저 소개하고, 다른 사람의 코드 중에 좋은 알고리즘을 소개하겠습니다.

바로 시작하겠습니다.

---

1. 내코드

백준 리뷰 문제 첫번째는 2805번 나무 자르기 문제입니다. (문제에 대한 설명은 생략하겠습니다.)

사용된 알고리즘: 이진 탐색

def check_func(list, h, d):
    sum_t = 0
    for t in list:
        if t <= h:
            break
        sum_t += t - h
    if sum_t >= d:
        return True
    else:
        return False

먼저 나무의 잘려진 부분이 목표치에 도달하는가를 체크해주는 함수부분입니다.

입력값: 나무리스트 - list, 시도해보는 높이 - h, 자르고자 하는 목표 높이 값 - d

나무리스트는 내림차순으로 정렬되어 함수에 들어오게 됩니다.

그래서 각 나무를 h와 비교하며 h보다 크다면 잘려지게 될테니 그 값을 sum_t 변수에 더해 저장합니다.

만일 나무 높이가 h보다 작다면 내림차순으로 정렬되어 있으니 그 뒤 나무들은 볼 필요가 없어 for문을 나가게 됩니다.

반복문이 끝나면 d와 비교해서 목표치를 이루었다면 True를, 이루지 못했다면 False를 반환합니다.

---

이제 메인 흐름입니다.

import sys
def check_func(list, h, d):...

input = sys.stdin.readline

N, M = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort(reverse=True)

height_limit_up = trees[0] - M // N 
height_limit_down = (sum(trees) - M) // N

height_guess = (height_limit_up + height_limit_down) // 2
current_height = 0
while height_limit_down <= height_limit_up:
    if check_func(trees, height_guess, M):
        current_height = height_guess
        height_limit_down = height_guess + 1
    else:
        height_limit_up = height_guess - 1
    height_guess = (height_limit_up + height_limit_down) // 2

print(current_height)

입력값들을 입력받고 내림차순으로 정렬합니다.

그리고 저는 이진탐색을 1부터 최대 높이의 나무까지 한게 아니라 범위를 좁혀줬습니다. (이 부분때문인지 이진탐색을 사용한 다른사람의 코드보다 제 코드가 시간이 조금 덜 걸리더군요)

이를테면, 나무가 10, 8, 6, 2 이고, 목표값이 8이라면, 10m나 9m는 볼 필요가 없을 것입니다.

왜냐하면, 목표값인 8m를 자르기 위해서는 모든 나무가 최대의 높이를 가지고 있다고 하더라도 2m가 잘려야하기 때문입니다.

마찬가지로 최소한의 높이도 정해줄 수 있습니다. 나무들의 총합에서 목표값을 뺀 값을 나무의 수로 나눠주면 그 몫을 최소의 높이로 정해줄 수 있습니다.

이렇게 최대의 높이 - height_limit_up, 최소의 높이 - height_limit_down을 정해줬습니다.

---

그 다음 최대와 최소를 더한 값의 절반을 추측값으로 두고 이진탐색을 시작합니다.

check_func에다가 나무리스트 - trees, 추측높이 - height_guess, 목표값 - M을 넣어주며 추측높이로 원하는 목표값을 얻을 수 있는지 확인합니다.

만약 추측높이가 되지않는다면, 추측값을 최대의 높이로 두고 또 이진탐색을 시작합니다.

만일 추측높이가 됬다라고 한다면, 추측값을 최소의 높이로 두고 이진탐색을 시작합니다.

이 과정들을 통해서 최적의 높이를 찾아냅니다. 최적의 높이란 쓸데없이 자르는 부분을 최소화하여 목표값과 가장 근접하게 자를 수 있는 높이를 가르킵니다.

---

2. 다른 방법

저는 늘 제 코드를 완성하고 다른 사람의 코드들도 살펴봅니다. 이번 문제도 그러던 중 생각지 못한 알고리즘이 있어 소개해보려고 합니다. 그런데 제 코드가 아니여서 이분의 아이디를 밝혀야 하는지 저작권이 있는건지 모르겠네요..

무조건 아이디를 공개하는 것도 좋은 방법인지 모르겠어서, 일단 그냥 써보고 문제가 있다면 수정하겠습니다.

먼저, 이분의 코드를 그림으로 그려보았습니다.

나무 리스트

각 나무가 내림차순으로 정렬되어 있습니다.

가장 처음 0번째 나무와 1번째 나무의 높이 차이를 구합니다. 그럼 빨간색 선 윗부분이 잘리겠죠? 이 높이가 목표값에 달하는지 확인합니다.

목표값에 도달하지 못했다면, 그 다음 1번째 나무와 2번째 나무의 차이를 구합니다. 그리고 위에서 구했던 빨간색 부분과 더합니다. 그러면 주황색 선 윗부분 전체가 되겠죠? 이 부분이 목표값에 달하는지 확인합니다.

이런식으로 이분의 코드에서는 각 나무들의 차이가 기준점이 되어 각 기준마다 목표값을 자를 수 있는지를 비교합니다.

그리고서 목표값을 자를 수 있는 높이를 찾았다고 한다면 세부 높이를 정하게 됩니다.

이를테면 노란색 선이 목표값을 자를 수 있었다고 한다면, 노란색 선과 주황색 선 사이에서 최적의 높이를 찾는 것입니다.

이제 알고리즘을 소개했으니 코드를 보여드리겠습니다.

---

N, M = map(int, input().strip().split())
trees = list(map(int, input().strip().split()))
trees.sort(reverse = True)
trees.append(0)

s = 0

for cnt in range(1, N+1):
	l = trees[cnt]
    s += (trees[cnt-1] - trees[cnt]) * cnt
    
    if s >= M:
    	min_l = trees[cnt]
        break
 
result = min_l + (s-M) // cnt
print(result)

코드가 굉장히 간결하고 알고리즘도 너무 좋은 것 같습니다.

저기 result = min_l + (s-M) // cnt 부분이 최적의 높이를 찾는 부분입니다.

이 코드를 보며 놀랐던 부분은 다른 사람들은 Python3를 PyPy3로 바꿈으로서 시간을 줄이던데, 이 분의 코드는 Python3를 쓰고서 800ms정도의 시간이 걸린 것입니다. (위의 제 코드는 Python3로 1740ms, PyPy3로 496ms가 걸렸습니다.)

게다가 sys.stdin을 사용한 입력이 아닌 input()함수를 사용했습니다. 흠... 근데 이건 입력받는 작업이 많지 않으니까 어쩌면 큰 영향을 주지 않을지도 모르겠습니다.

---

그럼 이번 문제는 여기까지 하겠습니다.