문제 출처 : https://www.acmicpc.net/problem/14247
14247번: 나무 자르기
영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다. 따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데, 나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오
www.acmicpc.net
이 문제는 현재 나무들의 높이와 가중치가 주어지는데 탐욕법을 이용하여서 가중치 순으로 정렬을 한 뒤
가중치가 작은 순서대로 자르면 답이 나오는 문제이다.
아래는 해당 문제를 풀이한 소스 코드이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include<stdio.h>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
struct list
{
int tree_height;
int increase;
};
list arr[100001];
bool compare(const list & a, const list & b)
{
return a.increase < b.increase;
}
int main()
{
int n;
long long int value = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i].tree_height);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i].increase);
sort(arr, arr + n, compare);
for (int i = 0; i < n; i++)
value = value+ arr[i].tree_height + i * arr[i].increase;
printf("%lld", value);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'알고리즘' 카테고리의 다른 글
| 백준 5427번 문제 ( 불 ) (0) | 2020.02.18 |
|---|---|
| 백준 2206번 문제 ( 벽 부수고 이동하기 ) (0) | 2020.02.14 |
| 백준 5014번 문제 ( 스타트링크 ) (0) | 2020.02.14 |
| 백준 3078번 문제 ( 좋은 친구 ) (0) | 2020.02.11 |
| 백준 17466번 문제 ( N! mod P ) (0) | 2020.02.11 |
뀨심볼
깃허브 주소는 : https://github.com/hhyc2 입니다~