백준 7578 c++ "공장" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리 자료구조를 이용하여 풀 수 있는 문제이다.

다만 사고 과정이 어렵다.

처음 모든 세그먼트 트리를 0으로 초기화 해놓고

A를 보면 132는 B에서 idx 3번에 해당한다.

그러면 세그먼트 트리를 3번부터 N까지 Query를 날려 그 구간에 갯수가 있으면 결과에 더하는 형식으로 코드를 작성하면 된다. Query를 날리고 나서 3번 idx에 세그먼트 트리를 Update해 하나를 더해주면 선분이 완성된다.

위와 같은 과정을 반복 하면 된다.

[코드 해설]

 

• Input 함수
  Input 함수는 프로그램에 필요한 입력 데이터를 처리합니다.
  • 먼저, 수열의 크기 N을 입력받습니다.
  • 크기가 N인 배열 A에 수열의 값을 입력받아 저장합니다.
  • 그다음, 또 다른 수열을 입력받아, 각 값이 몇 번째 위치에 있는지를 나타내는 map 자료구조 B에 1부터 시작하는 인덱스로 저장합니다.
• Query 함수
  이 함수는 세그먼트 트리를 이용해 특정 구간의 합을 계산합니다.
  • 만약 현재 노드의 구간이 쿼리 구간에 완전히 포함된다면, 해당 노드의 값을 반환합니다.
  • 현재 노드의 구간이 쿼리 구간과 전혀 겹치지 않으면 0을 반환합니다.
  • 그 외의 경우, 구간을 반으로 나누어 왼쪽 자식과 오른쪽 자식에 대해 재귀적으로 Query를 호출하고, 두 결과를 더해 반환합니다.
• Update 함수
  이 함수는 세그먼트 트리에서 특정 인덱스(idx)의 값을 주어진 차이(diff)만큼 업데이트합니다.
  • 만약 현재 노드가 단일 원소를 나타내는 경우, 그 노드의 값을 diff만큼 증가시킵니다.
  • 그렇지 않으면, 구간을 반으로 나누어 인덱스에 따라 적절한 자식 노드에 대해 재귀적으로 Update를 호출합니다.
  • 자식 노드의 값이 변경되면, 부모 노드의 값도 두 자식 노드의 합으로 갱신됩니다.
• Game_Start 함수
  이 함수는 입력 데이터를 처리하여 세그먼트 트리를 이용해 결과를 계산합니다.
  • 세그먼트 트리는 최대 N * 4 크기로 초기화됩니다.
  • 배열 A의 각 원소에 대해 다음 작업을 수행합니다:
    • 현재 원소의 위치를 B에서 찾아옵니다.
    • Query 함수를 사용하여 이미 처리된 원소 중 현재 위치보다 크거나 같은 위치에 있는 원소의 개수를 구합니다.
    • Update 함수를 사용하여 현재 위치를 처리했음을 세그먼트 트리에 반영합니다.
  • 이러한 작업을 통해 계산된 결과값을 resultCount에 누적하며, 최종적으로 이 값을 출력합니다.
• Main 함수
  main 함수는 빠른 입출력을 설정하고, Input 함수와 Game_Start 함수를 호출하여 프로그램을 실행합니다.

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<long>tree;
int N;
vector<long> A;
map<long, long> B;

void Input() {
	cin >> N;

	A.resize(N);

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		long num;
		cin >> num;
		B[num] = i+1;
	}
}

long Query(int Node, int start, int end, int left, int right) {
	if (left <= start && end <= right)return tree[Node];
	else if (end < left || right < start)return 0;
	else {
		int mid = (start + end) / 2;
		
		return Query(Node * 2, start, mid, left, right) +
			Query(Node * 2 + 1, mid + 1, end, left, right);
	}
}

void Update(int Node, int start, int end, int idx, long diff) {
	if (start == end) {
		tree[Node] += diff;
		return;
	}

	int mid = (start + end) / 2;
	if (mid >= idx) {
		Update(Node * 2, start, mid, idx, diff);
	}
	else {
		Update(Node * 2 + 1, mid + 1, end, idx, diff);
	}

	tree[Node] = tree[Node * 2] + tree[Node * 2 + 1];
}


void Game_Start() {

	tree.resize(N * 4 + 1);

	long resultCount = 0;

	for (int i = 0; i < N; i++) {
		long num = A[i];
		int nowIdx = B[num];

		resultCount += Query(1, 1, N, nowIdx, N);
		Update(1, 1, N, nowIdx, 1);

	}
	cout << resultCount << '\n';
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	Input();
	Game_Start();
}