[백준 14247번/c++] 나무자르기

알고리즘

• 그리디 알고리즘
• 정렬

 

---

풀이

나무 중 자라는 길이가 큰 것을 가장 나중에 자르도록 한다.

첫날 나무의 길이에 매일 자라는 길이만큼 더해지므로,

1. 정수 ans 변수에 첫날 나무의 길이를 다 더해둔 후
2. 매일 자라는 길이 * 자르기 전까지 자라난 일 수를 반복문을 통해 더해준다.
   • 매일 자라는 길이는 오름차순 정렬 후 배열의 끝에서부터 사용하였다.

 

---

시간 초과 코드

• grow 배열을 정렬하지 않고 굳이 max 값을 일일이 구하여 O(n^2) 시간복잡도가 되어 시간초과 발생

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    // freopen("input.txt", "rt", stdin);
    int n, max_index, ans=0;
    cin >> n;
    vector<int> tree(n), grow(n);

    for(int i=0; i<n; i++){
        cin >> tree[i];
    }
    for(int i=0; i<n; i++){
        cin >> grow[i];
    }
    // 하루에 자라는 길이가 제일 큰 것부터
    for(int i=n-1; i>=0; i--){
        max_index=max_element(grow.begin(), grow.end())-grow.begin();
        ans+=tree[max_index]+grow[max_index]*i;
        grow[max_index]=-1; // 다음 번에 사용되지 않도록
    }
    cout << ans;

    return 0;
}

 

---

자료형으로 틀린 코드

• int형이 아닌 long long형을 사용하여야 하는데 그렇게 하지 않아 틀림

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    // freopen("input.txt", "rt", stdin);
    int n, max_index, ans=0;
    cin >> n;
    vector<int> tree(n), grow(n);

    for(int i=0; i<n; i++){
        cin >> tree[i];
        ans+=tree[i];
    }
    for(int i=0; i<n; i++){
        cin >> grow[i];
    }
    sort(grow.begin(), grow.end());

    // 하루에 자라는 길이가 제일 큰 것부터
    for(int i=n-1; i>=0; i--){
        ans+=grow[i]*i;
    }
    cout << ans;

    return 0;
}

 

---

성공 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    // freopen("input.txt", "rt", stdin);
    int n;
    long long ans=0;

    cin >> n;
    vector<int> tree(n), grow(n);

    for(int i=0; i<n; i++){
        cin >> tree[i];
        ans+=tree[i];
    }
    for(int i=0; i<n; i++){
        cin >> grow[i];
    }
    sort(grow.begin(), grow.end());

    // 하루에 자라는 길이가 제일 큰 것부터
    for(int i=n-1; i>=0; i--){
        ans+=grow[i]*i;
    }
    cout << ans;

    return 0;
}