[백준] 골드4 : (30885) Φ²

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

 

먼저, 문제 설명을 잘못 해석하기 쉽기 때문에, 문제 조건부터 보자.

다음과 같은 입력의 전개이다.

4
1 3 4 2

 

1 -> 3 -> 4 -> 2 순으로 흡수를 진행한다.

 

자신과 인접한, 즉 왼쪽 - 오른쪽의 미생물에 대해서만 흡수를 시도할 수 있다.

현재 날의 크기를 기준으로 자신보다 크기가 작거나 같은 미생물을 흡수한다. << 핵심

 

1의 경우, 먹을 수 있는 게 없으니 넘어간다.

 

3의 경우, 왼쪽을 먹고 4가 된다.

여기서, 4가 되었으니 오른쪽의 4를 먹을 수 있지 않나? 하는 의문이 생긴다.

 

조건 3의 "흡수하는 미생물은 하루에 흡수할 모든 미생물을 한 번에 흡수한다" 라는 문구를 보자.

3을 기준으로 한 번에 왼쪽 와 오른쪽을 흡수해야 하므로, 흡수를 시작할 때의 크기를 기준으로 계산해야 한다.

따라서 다음과같이 전개된다.

1 3 4 2

4 4 2

4 6

10

Answer
10
3

 

 

이제 코드 구조를 보자.

문제를 보면 알겠지만, 미생물이 연결되어 있는 구조가 연결 리스트와 같다.

따라서, 처음 미생물의 위치, 현재 미생물의 크기, 이전 / 다음 순서의 미생물 데이터를 가진 구조체를 선언하여 관리한다.

 

처음 미생물들의 연결을 위해, 배열로 저장 후, 연결이 끝나고 나서 배열은 제거해 줬다.

 

미생물들이 서로 연결되는 노드 구조는 다음과 같이 설계했다. (연결 리스트와 같음)

[전전] - [전] - [나] - [후] - [후후]

 

[나]가 [전]을 먹는 경우

[전전]의 다음 미생물을 [나]로 갱신

[나]의 이전 미생물을 [전전]으로 갱신

 

[나]가 [후]를 먹는 경우

[후후]의 이전 미생물을 [나]로 갱신

[나]의 다음 미생물을 [후후]으로 갱신

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

struct Microbe
{
public:
	// 번호와 값 생성자 초기화
	Microbe(const int& InIndex, const long long& InSize)
		: Index(InIndex), Size(InSize), Prev(nullptr), Next(nullptr) {
	}

	int Index;
	long long Size;

	Microbe* Prev; // 이전 순서 미생물
	Microbe* Next; // 다음 순서 미생물
};

// 이전 순서 미생물을 먹는 함수
void PrevEat(Microbe& Current)
{
	// [전전] [전] [나] [후] [후후]

	Microbe* Prev = Current.Prev->Prev; // 전전 순서의 미생물을 복사하여 저장
	Microbe* Next = Current.Prev->Next; // 나를 복사하여 저장

	// 전 순서 미생물의 크기를 더하여 저장
	Next->Size += Current.Prev->Size;

	// 전전 미생물의 다음 순서를 나로 저장 [전전 / 후후는 없을 수 있음]
	if (Prev) Prev->Next = Next;
	Next->Prev = Prev ? Prev : nullptr; // 나의 이전 순서를 전전 미생물로 저장

	// 새로 구성한 미생물로 현재 미생물을 갱신
	Current = *Next;
}

// 다음 순서 미생물을 먹는 함수
void NextEat(Microbe& Current)
{
	Microbe* Prev = Current.Next->Prev;
	Microbe* Next = Current.Next->Next;
	Prev->Size += Current.Next->Size;

	if (Next) Next->Prev = Prev;
	Prev->Next = Next ? Next : nullptr;
	Current = *Prev;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	// 미생물 연결을 위한 임시 배열
	vector<Microbe> Microbes;

	for (int i = 1; i <= N; ++i)
	{
		long long j;
		cin >> j;
		Microbes.push_back(Microbe(i, j));
	}

	// 미생물 연결
	for (int i = 0; i < N; ++i)
	{
		if (i != 0) Microbes[i].Prev = &Microbes[i - 1];
		if (i < N - 1) Microbes[i].Next = &Microbes[i + 1];
	}

	// 가장 첫 미생물로 시작
	Microbe Current = Microbes[0];
	Microbes.clear(); // 미생물 저장 배열은 더 이상 필요없으니, 제거

	// 미생물이 하나만 남을 때 까지 반복
	while (Current.Prev || Current.Next)
	{
		// 미생물의 기본 크기
		const long long Size = Current.Size;

		// 이전 순서 미생물이 존재하고, 자신보다 크기가 작거나 같으면 먹음
		if (Current.Prev && Size >= Current.Prev->Size) PrevEat(Current);

		// 다음 순서 미생물이 존재하고, 자신보다 크기가 작거나 같으면 먹음
		if (Current.Next && Size >= Current.Next->Size) NextEat(Current);


		// 다음 순서 미생물로 이동
		if (Current.Next) Current = *Current.Next;
		// 현재 미생물의 다음 순서 미생물이 없는 경우, 연결된 첫 번째 미생물로 이동
		else while (Current.Prev) Current = *Current.Prev;
	}

	cout << Current.Size << "\n" << Current.Index << "\n";
}