[백준/C++] Pho Restaurant

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 두 가지 요리만 하는 식당에 n개의 테이블이 있고, n개의 테이블당 i명의 사람이 요리를 시킨다.

 

이때, 같은 테이블은 같은 요리를 주문하도록 만드려면 사람을 몇 번 이동해야하는지 계산하는 문제다.

 

문제 자체는 크게 어렵지 않다.

테이블 당 1번 메뉴와 2번 메뉴를 주문한 사람의 수를 파악하고, 그 중에서 메뉴의 수가 더 적은 사람을 다른 테이블로 이동시키면 된다.

 

여기서 하나의 예외 상황이 발생하는데, 만약 모든 테이블이 1번 메뉴를 많이 시키고 2번 메뉴를 적게 시키는 경우다.

(또는 모든 테이블이 2번 메뉴를 많이 시키고 1번 메뉴를 적게 시키는 경우)

 

이 경우 최소값인 수만 다른 테이블로 이동하면 안된다. 

 

테이블의 개수가 정해져 있기 때문에 적어도 하나의 테이블은 2번 메뉴만 모여야 되기 때문이다.

즉, 하나의 테이블은 2번 메뉴를 시킨 사람을 이동 시키는게 아니라 1번 메뉴를 시킨 사람을 이동시켜야 한다는 것이다.

 

이제 어떤 테이블을 1번 메뉴를 시킨 사람을 이동시킬지 정하는 방법은 다음과 같다.

 

1번 메뉴를 시킨 사람의 수를 m, 2번 메뉴를 시킨 사람의 수를 n이라고 하자.

그러면 이 테이블은 m명의 사람을 옮기거나 n명의 사람을 옮겨야한다.

 

그러므로 m - n의 절대값이 가장 작은 테이블을 1번 메뉴를 시키도록 하면 된다.

(m-n의 차가 작다는 것은 m을 옮기나 n을 옮기나 비슷하기 때문에, 증가하는 횟수가 가장 적게 된다는 뜻이다.)

 

이후 m-n의 절대값을 이동 횟수에 더해주면, i 테이블은 2번 메뉴를 시킨 사람 대신 1번 메뉴를 시킨 사람을 이동하는 것과 같은 결과가 된다.

 

 

​

[아이디어 정리]

1. 1번 메뉴와 2번 메뉴를 시킨 사람의 수를 비교하고 더 작은 값을 더한다.
2. 만약 모든 테이블에서 특정 메뉴가 더 많다면, 적어도 한 테이블은 다른 메뉴를 시킨 사람을 옮겨야 한다.
3. 다른 메뉴를 시킨 사람을 옮길 테이블은 두 메뉴의 차가 가장 작은 테이블이다.
4. 만약 a테이블은 1번 메뉴, b 테이블은 2번 메뉴를 시킨 사람이 많다면, 최소값만 더하면 된다.

 

 

 

Code

 

 

#include <iostream>
using namespace std;

const int INF =50000000;
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int S;
	cin >> S;
	string a;
	int minV= INF, maxV = -INF;
	int ans = 0;
	bool flag1 = false, flag2 = false; // 아예 옮기지 않아도 되는지 판단 하기 위함
	for (int j = 0; j < S; j++) 
	{
		cin >> a;
		int tZ = 0, tO = 0;
		for (int i = 0; i < a.length(); i++) 
		{
			if (a[i] == '0') {
				tZ += 1;
				flag1 = true;
			}
			else 
			{
				tO += 1;
				flag2 = true;
			}
		}
		minV = min(minV, tZ - tO), maxV = max(maxV, tZ - tO);
		ans += min(tZ, tO);
	}
	if (!flag1 || !flag2) {
		cout << 0;
		return 0;
	}
	if (minV < 0 && maxV < 0) { // 적어도 한 테이블은 최소값을 못 더하는 경우
		ans -= maxV;
	}
	else if (minV > 0 && maxV > 0) { // 적어도 한 테이블은 최소값을 못 더하는 경우
		ans += minV;
	}
	cout << ans;
	return 0;
}

 

---

처음에 min, max 범위를 너무 적게 잡고, 아예 옮기지 않아도 되는 경우를 처음에 빼먹어서 오답처리가 됐었다

그래도 빠르게 발견해서 쉽게 해결할 수 있었다.

 

31600번: Pho Restaurant