문제 링크
https://atcoder.jp/contests/abc420/tasks/abc420_b
알고리즘
구현, 문자열
시간복잡도
$O(NM)$
풀이
최대 점수를 직접 구할 필요는 없으므로 상대 점수만 고려합시다.
$X = 0$이거나 $Y = 0$인 상황은 모두의 점수가 증가하므로 무시할 수 있습니다. 아닌 상황은 문제의 지문대로
-
$X < Y$인 경우 $1$을 투표한 사람들에게 전부 $1$점을 줍시다.
-
아닌 경우 $0$을 투표한 사람들에게 전부 $1$점을 줍시다.
이후, 최댓값을 구한 다음 $1$번 사람부터 순차적으로 보면서 최댓값과 같은 값을 가지는 사람들을 전부 출력해주면 됩니다. 이는 전부 for문을 활용하여 구현할 수 있습니다.
소스코드
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string.h>
#include <map>
#include <queue>
#include <unordered_map>
using namespace std;
typedef long long ll;
ll score[105];
char s[105][105];
int main()
{
ll t = 1;
while(t--)
{
ll i,j,n,m,mx = -1;
scanf("%lld %lld",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%s",s[i]);
}
for(i=0;i<m;i++)
{
ll x,y = 0;
for(j=1;j<=n;j++)
{
if(s[j][i]-'0')y++;
}
x = n - y;
if(y == 0 || x == 0)continue;
if(y > x)
{
for(j=1;j<=n;j++)
{
if(!(s[j][i]-'0'))score[j]++;
}
}
else
{
for(j=1;j<=n;j++)
{
if(s[j][i]-'0')score[j]++;
}
}
}
for(i=1;i<=n;i++)
{
if(score[i] > mx)mx = score[i];
}
for(i=1;i<=n;i++)
{
if(score[i] == mx)printf("%lld ",i);
}
}
}
Comments