[백준 / BOJ] C++ 27919 UDPC 파티

27919번: UDPC 파티

 

문제

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

27919번: UDPC 파티

 

 

풀이

U와 C, D와 P를 같은 문자로 생각하고 개수를 센다. D와 P는 둘 다 선정되거나 둘 다 선정되지 않을 수 밖에 없다. U와 C의 수를 UC, D와 P의 수를 DP라고 할 때 U가 선정되기 위해서는 UC의 수가 (DP의 수 + 1) / 2보다 커야한다. 이유는 UC가 2, DP가 4일 때 DP를 2, 2로 나누어도 U가 각각보다 크지 못하므로 U가 선정될 수 없다. 그리고 DP가 5인 경우에도 나누기를 하면 2, 2가 되기 때문에 +1을 한 다음 연산을 해준다. 그리고 D와 P가 선정될 수 있는 경우는 DP의 수가 0보다 클 때이다. 왜냐하면 UC의 수가 얼마이든 모두 C로 간주하면 U의 투표수는 0이기 때문이다. 대회 때 실수를 많이한 문제다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string V, ans = "";
  cin >> V;
  int uc = 0, dp = 0;
  for (char i : V)
    if (i == 'U' || i == 'C')
      uc++;
    else
      dp++;
  if (uc > (dp + 1) / 2)
    ans += 'U';
  if (dp > 0)
    ans += "DP";
  cout << ans;
  return 0;
}