[백준][C++] 18234 당근 훔쳐 먹기

18234번: 당근 훔쳐 먹기

 

요즘엔 발상을 하는 데에 시간이 조금 걸리지만, 그 발상을 구현하는 데에 나는 오류나 한계가 줄어든 것 같아서 기분이 좋다! 이 문제도, 발상은 꽤 시간이 걸렸다만, 그걸 구현하는 과정 자체는 나름 노련하게 한 것 같아 기분이 좋다 ^__^

 

 

문제

 

 

발상

당근을 뽑지 않는다면, 당근은 배로 계속, 더 맛있어진다! 가장 핵심적인 문제의 내용이다. 

 

항상 w[i] <= p[i]이므로 하루를 기다리면, 적어도 배로 맛있어지는 것이다! 만약, 저 조건이 없었더라면...

 

1 3
10000 9999

이러한 입력이라면, 묻지도 따지지도 않고 3일을 모두 당근을 먹는 게 인지상정이다. 3*10000 > 10000+9999*2이기 때문! 하지만, 저 조건이 있기 때문에

 

1 3
10000 10001

이렇게 되니, 3*10000 < 10000+10001*2 이런 식이 나오게 되며 무조건 2일을 기다리는 것이 가장 최고의 당근을 맛볼 수 있는 것이다.

 

 

나는 처음에 토끼는 당근을 먹을 수도 있고 먹지 않을 수도 있다는 아주 중요한 지문을 보지 못해 가장 낮은 걸 버리는 카드로 내내 뽑고, 나중에 몰아서 기다렸던 당근들을 뽑을까? 라는 생각도 했지만, 곧 당근을 먹지 않을 수도 있다는 말에 모두 기다리기로 마음먹었다.

 

 

그렇다면 뽑는 순서는 어떻게 정해야 할까? 모두 기다리는 발상을 한 순간, 순서는 간단한 문제였다. 가장 p[i]가 가장 작은 것부터 뽑는 것이다. w[i]가 아무리 커도, 곱셈이 아니라 덧셈이기 때문에 향상되는 맛에 아무런 변화를 주지 못한다.

 

따라서, 쉽게 생각해 p[i]를 오름차순으로 정리해서 마지막에 파바바박 당근을 뽑아주면 된다!

 

 

알고리즘 설계

1. 당근을 p[i]의 값으로 오름차순 정렬한다.

 

2. 반복문을 당근의 횟수만큼 돌린다.

•  (T-N-i)날부터 순서대로 당근을 뽑는다.
• 뽑는 당근의 맛은 w[i] + p[i] * (T-N-i)
• 당근의 맛을 long long 변수에 저장한다.

3. 저장한 수를 출력한다.

 

 

코드

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

struct carrot
{
	unsigned long long w, p;

	bool operator < (const carrot& c) const
	{
		return p < c.p;
	}
};

vector<carrot> carrots;

int main()
{
	int len;
	long long int tCnt, res = 0;
	cin >> len >> tCnt;
	carrots.resize(len);

	for (int i = 0; i < len; i++)
	{
		cin >> carrots[i].w >> carrots[i].p;
	}

	sort(carrots.begin(), carrots.end());

	for (int i = 0; i < carrots.size(); i++)
	{
		res += carrots[i].w + carrots[i].p * (tCnt - len + i);
	}

	cout << res;
}