[백준] 14247 - 나무 자르기 (C++)

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

산에는 n개의 나무가 있고, 각각 나무의 현재 길이는 H_i이며 나무가 자라는 속도는 A_i이다. 영선이가 하루에 한 나무씩 n일 산에 오르며 나무를 자를 때, 영선이가 얻을 수 있는 나무의 양의 최댓값을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ n ≤ 100,000
• 1 ≤ H_i ≤ 100,000
• 1 ≤ A_i ≤ 10,000

 

나무마다 {H_i, A_i}를 쌍으로 저장하고, 하루에 한 나무씩 자를 수 있기 때문에 자라는 속도가 가장 작은 순서대로 나무를 잘라야 n일이 지났을 때 나무를 가장 많이 자를 수 있다. 따라서 pair<int,int>로 저장한 배열을 두 번째 원소를 기준으로 오름차순으로 정렬되게 하고, 앞에서부터 자른 나무의 양을 더하면 최대한 이득을 볼 수 있을 것이다. 자를 때는 H_i에 A_i를 현재 일수만큼 곱한 값을 더해야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. n 입력받기
2. H_i와 A_i 입력받기
3. A_i를 기준으로 {H_i, A_ㅑ} 쌍을 오름차순으로 정렬하고 A_i가 가장 작은 순서대로 나무 자르기
4. 나무를 잘라서 구할 수 있는 최대의 양 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
#define pii pair<int,int>
using namespace std;

int n,h[100001],a[100001];
long long int ans;
vector<pii> v;

bool cmp(pii a, pii b) {
    return a.second<b.second;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i=0; i<n; i++) cin >> h[i];
    for (int i=0; i<n; i++) cin >> a[i];

    for (int i=0; i<n; i++) v.push_back({h[i],a[i]});
    sort(v.begin(),v.end(),cmp);

    for (int i=0; i<n; i++) ans += v[i].first + v[i].second * i;

    cout << ans;
}