[백준/BOJ] 14247. 나무 자르기 [Silver 3]

14247. 나무 자르기

문제출처 : https://www.acmicpc.net/problem/14247

code

#include <stdio.h>
#include <stdlib.h>
int main()
{
	long long n, i, j, sum = 0;
	long long* Hi;
	long long* Ai;
	scanf("%lld", &n);
	Hi = (long long*)malloc(n * sizeof(long long));
	Ai = (long long*)malloc(n * sizeof(long long));
	for (i = 0; i < n; i++)
		scanf("%lld", &Hi[i]);
	for (i = 0; i < n; i++)
		scanf("%lld", &Ai[i]);
	for (i = 0; i < n; i++)
	{
		long long min = 10001, index = 0;
		for (j = 0; j < n; j++)
			if (min > Ai[j])
			{
				min = Ai[j];
				index = j;
			}
		sum += Hi[index]+(Ai[index]*i);
		Ai[index] = 10002;
	}
	printf("%lld", sum);
	free(Hi);
	free(Ai);
	return 0;
}

나무가 자라는 길이배열Ai가 작은 순서대로 더해주면 된다는거는 알겠는데, 코드를 잘못짜겠다 ㅠㅠ VS에서는 잘돌아가는데 제출하면 시간초과에 틀렸다고 계속뜬다 ㅠㅠ

해결했다.

생각해보니까 Hi를 Ai에 맞춰서 일일이 다 더할필요가없었다.
어차피 다짜를거니까 Hi는 입력받는 동시에 모두 sum에 더해주고,
Ai, 즉 자라는 속도는 오름차순 정렬을해서 인덱스만큼 곱해서 더해주면 된다.
.......

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long Hi[100000];
long long Ai[100000];
int main()
{
	ios_base::sync_with_stdio(false);

	int n, i, j, min, index;
	long long sum = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> Hi[i];
		sum += Hi[i];
	}
	for (int i = 0; i < n; i++)
		cin >> Ai[i];

	sort(Ai, Ai + n);

	for (int i = 0; i < n; i++)
		sum += Ai[i] * i;

	cout << sum;

	return 0;
}