5주차 3번(나무자르기)

Hyo Kyun Lee·2021년 5월 14일

알고리즘

스파르타코딩클럽-스파르탄365

목록 보기

5/9

1.문제 링크

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

2. 풀이 전 계획과 생각

이분탐색법을 이용한 풀이방법은 무엇이 있을까 고민해보기
이분탐색이 어렵다면 다른 방법이 있을지 고민해보고, 로직 구현해보기

3-1. 유의할 점

조건

가져갈 수 있는 나무는 "절단기로 자른 나무"이다.

자른 나무들을 통해 최소 길이가 M이상의 경우가 가능해야 한다.

결론

자른 나무들을 통해 모든 경우의 수를 구할 필요는 없다.
경우의 수가 존재한다는 점이 중요 포인트!

자른 나무들을 모두 이었을때 최소 길이 M이상이면 경우의 수가
최소 1가지가 존재한다는 의미!

경우의 수가 최소 1가지 이상 존재할 수 있는 최대의 절단기 길이가 문제의 답!

3-2. 풀이의 핵심

방식 : 반복문
▶이분탐색법을 통한 로직은 더 생각해보기
구현방안 : 자른 나무의 길이를 배열에 넣고 그 합이 M이상인지 판단
중요사항 : 반복문/조건의 원활한 구현이 필요

3-3. 풀이

현재 로직은 반복을 두번하여 답을 구하고 있다.

get_tree_height_after_cut 함수에 배열을 return한 후,
이 배열을 인라인화 하면 아래 조건에 상관없이 반복을 모두 한다.

왜 반복이 두번 일어나고,
위 함수에 배열을 return을 하면 답이 달라지게 되는지 고민해보자!

import sys

N, M = map(int, sys.stdin.readline().split())
tree_height = list(map(int, sys.stdin.readline().split()))

def get_max_H (N, M, tree_height):

    tree_height_after_cut = []
    H = 0

    while H < max(tree_height):
        H = H + 1

        # 나무절단후 남아있는 나무의 길이를 배열에 저장하는 함수
        get_tree_height_after_cut(H, N, tree_height, tree_height_after_cut)

        # 남아있는 나무의 길이로 최소길이 M을 만들수있는 절단기의 최대길이를 반환해주는 함수
        print(H)

        if sum(tree_height_after_cut) < M:
            return H - 1
            break
        else:
            tree_height_after_cut.clear()
            continue


def get_tree_height_after_cut(H, N, tree_height, tree_height_after_cut):
    for i in range(N):
        if tree_height[i] > H:
            tree_height_after_cut.append(tree_height[i] - H)
        else:
            tree_height_after_cut.append(0)

get_max_H(N, M, tree_height)
print(get_max_H(N, M, tree_height))

4. 풀이하면서 고민했던 점

코드의 완성을 위해 더 생각해보기
▶ 왜 반복을 두번하는 것일까?
▶ 리팩토링 과정에서 배열을 return 하면 왜 답이 달라질까?
이분탐색법으로 이 문제를 어떻게 풀 수 있을까?

알고리즘을 구현하는데 너무 시간이 오래걸린다
다른 방향으로 생각하는 것도 중요하지만, 시간을 절약하는 것도 매우 중요하다.
10분내외로 생각하고 알고리즘 구현하는 것까지 가능하도록 꾸준히 연습해보자.
클린코드
하나의 코드에 모든 기능을 담지말고, 기능을 최대한 분산한다.
▶조건을 입력받아 결과를 return하는 로직(메인함수)
▶나무절단후 남아있는 나무의 길이를 배열에 저장하는 함수
~~▶남아있는 나무의 길이(배열)에서 절단기 최대길이를 반환해주는 함수~~
(>구현방법이 있을까?)
가독성이 좋은 코드, 이해가 쉬운 코드의 조건들을 생각해보자.
최대한 획기적이면서 신선한 로직만이 경쟁력!

5. 문제를 풀고 알게된 개념 및 소감

sys.stdin.readline()
input 메소드와 함께 숫자/문자를 입력받을 수 있는 메소드
기본적으로 문자열 형태로 입력받으며, 정수필요시 형태변환이 필요
max(list)
list의 최대값
list.clear()
list배열에 저장되어있는 값을 모두 삭제(empty)