백준 14247번 [나무 자르기](C++) -yes6686- 티스토리

백준 문제 풀이: 14247 [나무 자르기]

---

문제 링크: https://www.acmicpc.net/problem/14247

문제 설명:

나무 n개의 초기 높이와 시간당 자라는 높이가 주어집니다. 하루에 나무 한 그루를 자를 수 있을 때, 모든 나무를 자른 후의 총 나무 길이 합이 최소가 되도록 자르는 순서를 결정하고 그 최솟값을 구하는 문제입니다.

---

문제 해결 코드

// 백준 14247 - 나무 자르기
#include <iostream>
#include <algorithm>
using namespace std;

int growth[100001]; // 나무 성장률 배열
int height[100001]; // 나무 초기 높이 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 나무의 개수

    long long totalHeight = 0;

    // 초기 높이 입력
    for (int i = 0; i < n; i++) {
        cin >> height[i];
        totalHeight += height[i]; // 초기 높이를 결과에 추가
    }

    // 성장률 입력
    for (int i = 0; i < n; i++) {
        cin >> growth[i];
    }

    // 성장률 기준 오름차순 정렬
    sort(growth, growth + n);

    // 나무를 자르는 순서에 따라 추가 길이 계산
    for (int i = 0; i < n; i++) {
        totalHeight += (long long)growth[i] * i;
    }

    // 결과 출력
    cout << totalHeight << '\n';
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 나무를 자르는 순서를 성장률이 낮은 나무부터 진행하여 자라나는 높이의 영향을 최소화합니다.
• 구현 세부사항:
  • 모든 나무의 성장률을 오름차순으로 정렬합니다.
  • 각 나무의 성장률에 자르는 순서를 곱하여 추가 길이를 계산합니다.
  • 초기 높이의 합과 추가 길이의 합을 구해 결과를 출력합니다.
• 시간 복잡도 분석:
  • 성장률 정렬: O(n log n)
  • 추가 길이 계산: O(n)
  • 총 시간 복잡도: O(n log n)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!