BOJ 8714 - Monety

문제

BOJ 8714 - Monety

N개의 동전이 주어지고, 각 동전은 앞면(1) 또는 뒷면(0) 상태이다. 모든 동전을 같은 면으로 맞추기 위해 뒤집어야 하는 최소 동전 수를 구한다. 앞면으로 통일하려면 뒷면 동전 수만큼, 뒷면으로 통일하려면 앞면 동전 수만큼 뒤집으면 되므로 두 값 중 작은 것이 답이다.

입력

첫 번째 줄에 동전의 수 N이 주어진다. 다음 줄에 N개의 정수(0 또는 1)가 주어진다.

출력

모든 동전을 같은 면으로 맞추기 위해 뒤집어야 하는 최소 횟수를 출력한다.

예제

풀이

앞면(1)인 동전의 수를 세고, 전체에서 뺀 값(뒷면 수)과 비교하여 최솟값을 출력한다.

1. N을 입력받는다.
2. N개의 동전 상태를 순회하면서 앞면(1)인 동전 수 cnt를 센다.
3. 뒷면 수는 n - cnt이다.
4. min(cnt, n - cnt)를 출력한다.

핵심 아이디어: 두 가지 목표 상태(전부 앞면 / 전부 뒷면) 중 더 적은 뒤집기가 필요한 쪽을 선택하면 된다. 앞면 수와 뒷면 수 중 최솟값이 답이다.

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
int n, cnt;
 
int main()
{
  cin >> n;
  for (int i = 0, s; i < n; i++)
  {
    cin >> s;
    if (s)
      cnt++;
  }
  cout << min(cnt, n - cnt);
}

복잡도

• 시간: O(N) — 동전 N개를 1회 순회
• 공간: O(1) — 카운터 변수만 사용