나무꾼 이다솜 ( 1421 번 )

1421번: 나무꾼 이다솜

 

 

 

---

🧠 알고리즘

• 완전 탐색(Brute Force)

 

✔️ 동작 방식

• 절단 길이(lenth)를 1부터 가장 긴 나무 길이까지 반복
• 모든 길이에서의 이익 중 최댓값 출력

---

 

🧾 코드

import sys

def _cr_price(lenth, tree_len):
    answer = 0
    for tree in tree_len:
        split_ct = tree // lenth
        if split_ct == 0: # 조각이 안나오면.. bypass
            continue
        
        na = tree % lenth

        split_cost = (split_ct * c) if na else ((split_ct - 1) * c)

        now_cost = ((split_ct * w * lenth) - split_cost)
        
        if now_cost > 0: # 이득이 나는 경우 가져다 팔음!!
            answer += now_cost

    return answer


def _main():
    answer = 0
    tree_len = [int(sys.stdin.readline().rstrip()) for _ in range(n)]

    for lenth in range(1, max(tree_len) + 1):
        now_price = _cr_price(lenth, tree_len)
        answer = max(answer, now_price)
        
    return answer
    
n, c, w = map(int, sys.stdin.readline().rstrip().split())
print(_main())

---

 

⏱️ 시간 복잡도

for lenth in range(1, max(tree_len) + 1) : 절단 길이 순회 ( 선형 시간 )
    _cr_price(lenth, tree_len) : 나무를 순회하며 비용 증감 ( 선형 시간 )

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )

---