[BOJ][브1][14247] 나무 자르기

문제 링크

문제링크

첫 번째 풀이 : Greedy

알고리즘

n개의 나무가 있고 n번 자릅니다. 현재 길이가 가장 긴 나무를 자르는 것은 최적이 아닙니다. 만약 이 방법으로 두 번이상 잘리는 나무가 있다면, 가장 마지막에만 잘라도 같은 양을 얻을 수 있습니다. 그리고 남은 횟수는 자르지 않은 나무를 자르는데 사용하면 됩니다. 즉, 우선 모든 나무를 한 번씩 잘라야 합니다.

모든 나무를 한 번씩 자른다면, 빨리 자라는 나무를 늦게 잘라야 합니다.

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 100010;
const int MOD = 10007;
int arr[MAX];
pii arr2[MAX]; // first 자라는 길이, second index
//int dp[MAX][2];
//bool visited[MAX];
//
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };


int n, k;

void show(void);
void bfs(int x, int y);

int main()
{
    //freopen("input.txt", "r", stdin);
    //ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> arr2[i].first;
        arr2[i].second = i;
    }
    sort(arr2, arr2 + n);
    ll cnt = 0;
    ll ans = 0;
    for (int i = 0; i < n; i++, cnt++) {
        // 자라는 길이 * 날짜) + 초기 길이
        ans += (arr2[i].first * cnt) + arr[arr2[i].second];
    }
    cout << ans;
    return 0;
}

두 번째 풀이

#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int n = 0;
pair<int,int> arr[100100];
bool compare(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}
int main(void)
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i].first);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i].second);
    }
    sort(arr, arr+n, compare);
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        printf("%d %d\n", arr[i].first, arr[i].second);
        ans += arr[i].first + arr[i].second * i;
    }
    printf("%lld", ans);
    return 0;
}

Success Notice: 수고하셨습니다.