이번 문제는 2019 전북대학교 프로그래밍 경진대회 H번 문제입니다.
백준 17251 힘 겨루기 라는 문제에요
풀이
우선은 다들 보시자마자
각각의 사람들의 힘을 벡터나 배열에 넣어서 해결 해 보려고 생각 하셨을 거라고 생각합니다.
그러나 이 문제는 전혀 그럴 필요가 없습니다!
무조건 가장 힘이 쌘 사람에 의해서 게임이 결정 되기 떄문이죠
예를들면
? ? bigest ? ? ?
이런식으로 나머지 값은 전혀 모르더라도 제일 큰 값이 어디에 위치 해 있는지만으
왼쪽 팀이 승률이 더 높을지, 오른쪽 팀이 승률이 더 높을지 예상을 할 수 있습니다.
그렇다면 제일 큰 값이 여러개일때는 어떻게 해야 할까요?
마찬가지로 제일 큰 값들의 위치만 알아도 어느팀의 승률이 더 높을지 알 수 있습니다.
? bigest ? ? ? bigest
제일 큰값과 제일 큰 값 사이의 값은 모두 빼고 생각을 하고, 그 밖의 값들만 생각을 해 주면 됩니다.
이건 제일 큰값이 2개든 3개든 100만개든 똑같습니다.
그럼 이제 필요한건 제일 큰 값 , 제일 큰 값의 위치 만 있으면 이 문제는 끝나게 됩니다.
저는 값을 입력 받으면서 동시에 진행 하였습니다.
만약 값 = max => 큐에 위치 저장,
값 > max => 기존 큐를 비우고, max 값 갱신, 큐에 위치 저장
이런 식으로 해주시면 됩니다.
코드
#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;
int main() {
int n;
int temp=0;
int max = 0;
int left, right;
queue<int> maxn;
cin >> n;
for (int i = 0; i < n; i++) {
scanf(" %d", &temp);
if (temp > max) {
while (!maxn.empty())
maxn.pop();
maxn.push(i);
max = temp;
}
else if (temp == max) {
maxn.push(i);
}
}
if (maxn.size() == 1) {
left = maxn.front();
right = n - left-1;
}
else {
left = maxn.front();
while (!maxn.empty()) {
temp = maxn.front();
maxn.pop();
}
right = n - temp - 1;
}
if (left > right)
cout << "B";
else if (left < right)
cout << "R";
else
cout << "X";
return 0;
}