취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17251번 문제인 힘 겨루기이다.
문제는 아래 링크를 확인하자.

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

수 $k$가 뽑혔을 때 홍팀과 청팀 중 어느 팀이 이기는지(또는 비기는지) 여부는 1번부터 $k$번까지의 참가자 중 가장 센 사람과 $k+1$번부터 $N$번까지의 참가자 중 가장 센 사람의 세기를 비교해 구할 수 있다.

각 $k$값에 대해 위의 비교를 모두 하는 것은 1번부터 $k$번까지의 참가자 중 가장 센 사람의 세기를 모든 $k$에 대해 $O(N)$에 먼저 따로 구해두고, 비슷하게 $N$번부터 $k+1$번까지의 참가자들 중 가장 센 사람의 세기를 모든 $k$에 대해 $O(N)$에 구해둔다면 총 $O(N)$에 구해낼 수 있다.

각각의 $k$가 뽑힐 확률이 동일하므로 각 $k$값에 대하여 승리하는 경우의 수가 어느 팀이 더 많은지를 위의 방법으로 찾아 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int A[1000002];
int L[1000002], R[1000002];
int cntL, cntR;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= N; i++) L[i] = max(L[i - 1], A[i]);
	for (int i = N; i > 0; i--) R[i] = max(R[i + 1], A[i]);
	for (int i = 1; i < N; i++) {
		if (L[i] > R[i + 1]) cntL++;
		else if (L[i] < R[i + 1]) cntR++;
	}

	if (cntL > cntR) cout << 'R';
	else if (cntL < cntR) cout << 'B';
	else cout << 'X';
}