[코드트리] 코드트리 등산 게임 (삼성 SW 역량테스트 2024 하반기 오후 2번, B형)

 

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

삼성 B형 전체 링크

 

2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,

A형 1문제 + B형 문제 1문제가 출제됩니다.

 

참고 

- BOJ 10828 : 스택

- BOJ 12015 : 가장 긴 증가하는 부분 수열 2

 

https://www.codetree.ai/training-field/frequent-problems/problems/%08codetree-mountain-climbing-games

이후 설명 및 입/출력은 링크 참고

 

이 문제는 산의 높이가 주어질 때,

등산가는 현재 위치보다 오른쪽에 위치한 산 중, 현재 산 보다 높은 산으로만 움직일 수 있다.

케이블 카가 없다면, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 구하면 된다.

 

여기서 케이블은 반드시 타는 것이 점수를 높이는데 도움이 되므로 케이블 카는 반드시 타야한다.

즉, 케이블 카를 이용할 수 있는 산의 위치 m_index라면

"구간 [1, m_index]에서 LIS의 길이"와 "전체 구간 LIS의 길이"를 더한 값에 100만을 곱한 값이 정답이 된다.

 

등산 시뮬레이션을 할 때, 최종적으로 위치한 산의 높이도 점수에 추가해야 하는데,

이 말은 부분 수열에서 같은 LIS의 길이가 여러 개일 때, LIS 중 가장 큰 값을 포함하는 수를 찾아야 한다는 뜻이 된다.

따라서, LIS의 길이를 세그먼트 트리에 저장할 때, 산의 높이도 같이 저장해서 문제를 해결할 수 있다.

 

BOJ 12015 : 가장 긴 증가하는 부분 수열 2에서 사용한 세그먼트 트리를 다음과 같이 수정할 수 있다.

newNode를 추가할 때,  산의 높이 height를 참고하여 maxNode를 갱신한다.

struct NODE
{
	int value;
	int height;
};

void update(int left, int right, int node, int index, NODE newNode)
{
	if (index < left || right < index) return;

	if (left == right)
	{
		tree[node] = newNode;
		return;
	}

	int mid = (left + right) / 2;
	int leftNodeIndex = node * 2;
	int rightNodeIndex = node * 2 + 1;

	update(left, mid, leftNodeIndex, index, newNode);
	update(mid + 1, right, rightNodeIndex, index, newNode);

	NODE leftNode = tree[leftNodeIndex];
	NODE rightNode = tree[rightNodeIndex];
	NODE maxNode;

	if (leftNode.value > rightNode.value) maxNode = leftNode;
	else if (leftNode.value == rightNode.value
		&& leftNode.height > rightNode.height) maxNode = rightNode;
	else
		maxNode = rightNode;

	tree[node] = maxNode;
}

 

그러면 getMax에서 리턴한 값이 가장 높이가 큰 산을 포함하는 LIS의 길이를 구할 수 있다.

NODE getMax(int left, int right, int a, int b, int node)
{
	if (b < left || right < a) return { 0, 0 };
	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	NODE leftNode = getMax(left, mid, a, b, node * 2);
	NODE rightNode = getMax(mid + 1, right, a, b, node * 2 + 1);
	NODE maxNode;

	if (leftNode.value > rightNode.value) maxNode = leftNode;
	else if (leftNode.value == rightNode.value
		&& leftNode.height > rightNode.height) maxNode = rightNode;
	else
		maxNode = rightNode;

	return maxNode;
}

 

여기서 가장 오른쪽부터 산이 추가되거나 삭제된다.

산이 추가되면 [1, m_index]에서 LIS의 길이는 상태가 바뀌게 된다.

따라서 산을 추가할 때 마다, answer[m_index]에 [1, m_index]에서 LIS의 길이를 저장해둔다.

 

산이 삭제되는 경우는 이전에 있었던 상태를 다시 세그먼트 트리에 갱신해야 된다.

산은 가장 오른쪽에서 추가되거나 삭제되므로 스택을 이용해서 처리할 수 있다.

---

빅뱅

 

산의 높이는 mountain 배열의 index 1부터 저장한다.

1부터 저장하기 때문에 mountain의 길이 mcnt는 N + 1이 된다.

 

현재 상태에서 입력되는 산의 높이의를 before에 미리 저장하고,

입력된 산의 높이와 구간 [1, 입력된 산의 높이]에서 LIS의 길이를 스택에 push한다.

그리고 [1, 입력된 산의 높이 - 1] 까지의 LIS의 길이를 구하고

이 값에 1을 더한 값을 높이와 함께 세그먼트 트리의 mountain[i]에 저장한다.

그리고 LIS의 길이를 answer에 저장한다.

void input()
{
	scanf("%d", &N);

	for (int i = 1; i <= N; i++) scanf("%d", &mountain[i]);
	mcnt = N + 1;

	for (int i = 1; i <= N; i++)
	{
		NODE current = getMax(1, MAX_H, mountain[i], mountain[i], 1);

		stack[sp].height = mountain[i];
		stack[sp++].value = current.value;

		NODE max = getMax(1, MAX_H, 1, mountain[i] - 1, 1);
		update(1, MAX_H, 1, mountain[i], { max.value + 1, mountain[i] });

		answer[i] = max.value + 1;
	}
}

---

우공이산

 

mountain에 입력된 산의 높이를 추가한다.

위와 같은 방식으로 현재 상태를 구해서 스택에 push하고,

세그먼트 트리와 answer에 LIS의 길이를 갱신한다.

void moveMountain(int height)
{
	mountain[mcnt++] = height;

	NODE current = getMax(1, MAX_H, height, height, 1);

	stack[sp].height = height;
	stack[sp++].value = current.value;

	NODE max = getMax(1, MAX_H, 1, height - 1, 1);	
	update(1, MAX_H, 1, height, { max.value + 1, mountain[mcnt - 1] });
	answer[mcnt - 1] = max.value + 1;
}

---

지진

 

mountain에서 가장 오른쪽 산을 삭제한다.

스택에서 pop을 한 후, 이전 상태를 세그먼트 트리에 다시 갱신한다.

void earthquake()
{
	int eqHeight = mountain[--mcnt];
	NODE before = stack[--sp];

	update(1, MAX_H, 1, eqHeight, { before.value, before.height });
}

---

등산 시뮬레이션

 

전체 구간에 대해 LIS의 길이를 getMax를 이용해서 구하고,

1부터 케이블 카가 존재하는 m_index 구간의 LIS의 길이는 적어둔 answer에서 구하면 된다.

getMax를 이용해서 얻은 total의 height가 LIS 중 가장 큰 산이 된다.

ll simulate(int m_index)
{
	NODE total = getMax(1, MAX_H, 1, MAX_H, 1);

	return ((total.value - 1) + answer[m_index]) * MAX_H + total.height;
}

---

전체 코드는 다음과 같다.

#include <stdio.h>

typedef long long int ll;

#define MAX_Q (500000 + 5000)
#define MAX_H (1000000)

#define BIGBANG (100)
#define MOVE_MOUNTAIN (200)
#define EARTHQUAKE (300)
#define SIMULATION (400)

int Q;
int mountain[MAX_Q];
int mcnt;

struct NODE
{
	int value;
	int height;
};

int N;
NODE tree[4004000];
int start;

NODE stack[MAX_Q];
int sp;

ll answer[MAX_Q];

void update(int left, int right, int node, int index, NODE newNode)
{
	if (index < left || right < index) return;

	if (left == right)
	{
		tree[node] = newNode;
		return;
	}

	int mid = (left + right) / 2;
	int leftNodeIndex = node * 2;
	int rightNodeIndex = node * 2 + 1;

	update(left, mid, leftNodeIndex, index, newNode);
	update(mid + 1, right, rightNodeIndex, index, newNode);

	NODE leftNode = tree[leftNodeIndex];
	NODE rightNode = tree[rightNodeIndex];
	NODE maxNode;

	if (leftNode.value > rightNode.value) maxNode = leftNode;
	else if (leftNode.value == rightNode.value
		&& leftNode.height > rightNode.height) maxNode = rightNode;
	else
		maxNode = rightNode;

	tree[node] = maxNode;
}

NODE getMax(int left, int right, int a, int b, int node)
{
	if (b < left || right < a) return { 0, 0 };
	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	NODE leftNode = getMax(left, mid, a, b, node * 2);
	NODE rightNode = getMax(mid + 1, right, a, b, node * 2 + 1);
	NODE maxNode;

	if (leftNode.value > rightNode.value) maxNode = leftNode;
	else if (leftNode.value == rightNode.value
		&& leftNode.height > rightNode.height) maxNode = rightNode;
	else
		maxNode = rightNode;

	return maxNode;
}

void input()
{
	scanf("%d", &N);

	for (int i = 1; i <= N; i++) scanf("%d", &mountain[i]);
	mcnt = N + 1;

	for (int i = 1; i <= N; i++)
	{
		NODE current = getMax(1, MAX_H, mountain[i], mountain[i], 1);

		stack[sp].height = mountain[i];
		stack[sp++].value = current.value;

		NODE max = getMax(1, MAX_H, 1, mountain[i] - 1, 1);
		update(1, MAX_H, 1, mountain[i], { max.value + 1, mountain[i] });

		answer[i] = max.value + 1;
	}
}

void moveMountain(int height)
{
	mountain[mcnt++] = height;

	NODE current = getMax(1, MAX_H, height, height, 1);

	stack[sp].height = height;
	stack[sp++].value = current.value;

	NODE max = getMax(1, MAX_H, 1, height - 1, 1);	
	update(1, MAX_H, 1, height, { max.value + 1, mountain[mcnt - 1] });
	answer[mcnt - 1] = max.value + 1;
}

void earthquake()
{
	int eqHeight = mountain[--mcnt];
	NODE before = stack[--sp];

	update(1, MAX_H, 1, eqHeight, { before.value, before.height });
}

ll simulate(int m_index)
{
	NODE total = getMax(1, MAX_H, 1, MAX_H, 1);

	return ((total.value - 1) + answer[m_index]) * MAX_H + total.height;
}

int main()
{
	scanf("%d", &Q);

	for (int q = 0; q < Q; q++)
	{
		int COMMAND;

		scanf("%d", &COMMAND);

		if (COMMAND == BIGBANG) input();
		else if (COMMAND == MOVE_MOUNTAIN)
		{
			int h;

			scanf("%d", &h);

			moveMountain(h);
		}
		else if (COMMAND == EARTHQUAKE)
		{
			earthquake();
		}
		else if (COMMAND == SIMULATION)
		{
			int m_index;

			scanf("%d", &m_index);

			printf("%lld\n", simulate(m_index));
		}
	}

	return 0;
}