치킨 날다

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

백준 사이트에서 풀 수 있는 정육점 문제입니다.

카테고리는 Greedy입니다.

19일 전에 처음 시도했던 이 문제를 중간에 과제 기간이라 하여 일주일 쉬긴 했지만 3주만에 드디어 풀었습니다.

풀면서 제가 막히거나 신경 쓴 부분은 다음과 같습니다.

1. 가격이 더 싼 고기를 무료로 얻을 수 있으므로 가격을 오른차순으롱 먼저 정렬하고,
무게를 빠르게 채워야 하므로 가격이 동일 한 경우 무게를 내림차순으로 정렬한다.

2. 가격이 더 싼 고기를 무료로 얻는다고 했지 가격이 같은 고기를 무료로 얻는다고는 안했다.

동일한 가격에 대해 누적된 가격을 계산해야 한다.

3. 2의 과정이 무게가 목표치보다 낮을 경우와 높을 경우에 필요한 연산이 다르다.

목표치보다 낮으면 항상 가격이 누적되고, 변동된 가격이 들어오더라도 이전 가격을 무시하면 된다.

반대로 목표치보다 높으면 가격을 더이상 누적하지 않고, 현재 최소 가격과 현재 가격만을 비교한다.

4. 모든 고기의 무게와 가격의 각 합인 unsigned int의 최대 값보다 작거나 같다.

때문에 조건에 부합하지 못해 -1을 출력해야 할 때 단순한 삼항연산자 등을 이용하면 <2^32 - 1>이 출력된다.
번거롭더라도 if문을 사용하거나, 출력 전에 string으로 형변환을 하는 등의 작업을 선행하자.

매우 간단하고, 처음에도 간단하다고 생각 했는데 3번 부분을 항상 놓치거나 잘못 작성하여 정답을 맞추지 못했다.

그리고 여태까지 문제를 풀면서 몇몇 문제는 정답 코드를 참조하기도 했는데,
이 문제는 정답률이 낮아서인지 마땅한 코드가 거의 없다.

아니, 그냥 검색 결과가 2개 정도 밖에 없다.

그래서 일부로 글 앞에 검색에 걸릴만한 내용을 추가하고, 하단에 코드를 작성했다.

이 문제에 막혀 참고를 하고자 하시는 분들은 다음 코드를 참고하시면 될 것 같다.

#include <iostream>
#include <vector>
#include <algorithm>

struct chunk {
	unsigned int weight;
	unsigned int price;
};

using namespace std;

int main()
{
	unsigned int length = 0, needs = 0, weight = 0, price = 0, before = -1;
	vector<struct chunk> meatlist;

	cin >> length >> needs;
	for (int i = 0; i < length; ++i)
	{
		cin >> weight >> price;
		meatlist.push_back(chunk{ weight, price });
	}

	sort(meatlist.begin(), meatlist.end(), [](const auto& a, const auto& b) { return ((a.price < b.price) || (a.price == b.price) && (a.weight > b.weight)); });

	weight = price = 0;

	for (const auto& iter : meatlist)
	{
		if (weight < needs)
		{
			if (before == iter.price)
			{
				price += iter.price;
			}
			else
			{
				before = price = iter.price;
			}
		}
		else
		{
			if ((before != iter.price) && (price >= iter.price))
			{
				before = price = iter.price;
			}
		}
		weight += iter.weight;
	}

	if (weight < needs)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << price << endl;
	}

	return 0;
}

혹 몇가지 testcase가 필요하신 분들은 아래 파일에 있는 것을 참고하시길.

유의미 하지는 않지만 그래도 없는 것 보다는 나을 것이다.

Puzzle을 기능 기준으로 수정 하려다가 수 많은 에러에 맞고 쓰러졌습니다.

Puzzle의 코어한 부분들이 모두 Blueprint로 구현되어 있었기에 기능 구현이고 뭐고
일단 C++ 스크립트로의 수정 과정이 선행 되어야 했습니다.

그래서 안타깝게도 하루만에 순서를 바꾸어 Interface 적용을 앞땡겼습니다.

Interface를 적용하고자 하는 부분을 탐색해보자 정말 수 많은 선택지가 펼쳐졌습니다.

그 중에서 단순 생성과 관련된 함수나, 외부에서 접근할 필요가 없는 트리거에 대한 변경 함수를 제외하고 
나머지 상태 확인이나 트리거 변경, 선언 함수들을 Interface로 엮었습니다.

그 결과는 다음과 같습니다.

이들을 하나씩 적용하고, 이미 기능이 적용 되어 있다면 이를 수정 할 예정입니다.

이 외에 변경점이라면 이전에 Climb 기능 구현을 하면서 터득한
Animation Notify를 이용해 Melee Attack 기능을 개선하고자 합니다.

우선 Hit 이벤트가 여러번 발생하는 것을 막아주는 Lock을 Semaphore로 변경하고자 합니다.

이를 통해 한 Character에게는 한번의 이벤트만 발생하지만, 한번에 여러 Character에게 이벤트가 발생할 수 있습니다.

그리고 데미지 계산이나 Semaphore 연산을 RPC 함수를 이용하고자 합니다.

그리고 Wall을 분할하고자 합니다.

현재의 Wall은 Character의 이동 경로를 막는 방해물과 등반 가능한 등반 Object가 동시에 혼용되고 있습니다.

이를 두개로 나누어 기존의 Wall은 후자의 것으로 사용하고, 

전자의 것에 어울리는 새로운 Object를 생성하고자 합니다.

마지막으로 Puzzle을 새로 개발하고자 합니다.

BP 기반에 이전 Trap에 너무 의존적이었기에 완전히 삭제하고, 새로운 Puzzle을 개발하고자 합니다.

이번에는 UI 등 편의성을 개선할 계획도 있습니다.

새로운 Puzzle은 기존의 Break, Select를 우선 구현하고, 새로운 것을 구현할지 그때 가서 고민하려 합니다.

진행 순서는

1. Character 자체 기능 개선

2. Wall 분할

3. Climb 기능 개선

4. Trap 기능 개선

5. Puzzle 생성

입니다.

#include <iostream>
#include <vector>
#include <algorithm>

struct chunk {
	unsigned int weight;
	unsigned int price;
};

using namespace std;

int main()
{
	unsigned int length = 0, needs = 0, weight = 0, price = 0, before = -1;
	vector<struct chunk> meatlist;

	cin >> length >> needs;
	for (int i = 0; i < length; ++i)
	{
		cin >> weight >> price;
		meatlist.push_back(chunk{ weight, price });
	}

	sort(meatlist.begin(), meatlist.end(), [](const auto& a, const auto& b) { return ((a.price < b.price) || (a.price == b.price) && (a.weight > b.weight)); });
	weight = price = 0;

	for (const auto& iter : meatlist)
	{
		if (weight < needs)
		{
			if (price > iter.price)
			{
				before = price = iter.price;
			}
			else
			{
				if (before == iter.price)
				{
					price += iter.price;
				}
				else
				{
					before = price = iter.price;
				}
			}
		}
		else
		{
			if ((price > iter.price) && (before != iter.price))
			{
				before = price = iter.price;
			}
		}
		weight += iter.weight;
	}

	if (weight < needs)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << price << endl;
	}

	return 0;
}

구상한 코드가 틀려 몇일 정도 다시 예외 상황이나 문제점을 고민해보도록 하겠습니다.