[S1] 백준 30406번 산타 춘배의 선물 나눠주기 C++ 그리디 알고리즘

리뷰

 

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

N개의 선물을 N/2 마리의 고양이에게 2개씩 나누어 주고, 각 선물의 번호를 XOR한 값의 합의 최대치를 구하는 문제

 

 

전역 변수

• n : 주어지는 선물의 개수를 저장할 변수
• ans : 정답을 저장하기 위한 변수
• cnt : 주어지는 선물 번호의 개수를 저장할 정수형 배열
• prio : 그리디한 선물을 배분하는 순서를 담은 정수형 2차 배열

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고 n개의 선물 정보를 입력 받는다, 입력 받은 선물 번호를 index로 cnt배열의 값을 증가시킨다.
2. 4 * 4크기의 for문을 개행해 준다, 만약 i번호를 가지는 선물이 존재하지 않으면 continue 처리해 준다.
3. i번호의 선물의 개수와, i번째 선물의 j번째 우선순위를 갖는 선물의 개수 중 작은 값을 변수 can에 저장해 준다.
4. ans에 i와 j번째 우선순위를 갖는 선물의 번호를 XOR연산한 값과 can을 곱한 값을 더해준다.
5. i번호의 선물과 j번째 우선순위를 갖는 선물의 개수를 can개씩 줄여준다.
6. for문이 종료될 때 까지 위 작업을 반복해준다.
7. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 2중 for문 안에서 i와 j의 인덱싱을 반대로 하지 않아 예제는 맞고 제출은 Fail을 받았다.
2. 우선순위가 높은 순서대로 탐색을 해야 하므로 j가 밖에, i가 안쪽에 있어야 한다.

 

참고 사항

• n값은 항상 짝수로 주어진다.
• 상품의 가격은 모두 0이상, 3이하의 정수이다.

 

정답 코드

#include<iostream>
using namespace std;

int n, ans;
int cnt[4];
int prio[4][4] = {
	{3, 2, 1, 0},
	{2, 3, 0, 1},
	{1, 0, 3, 2},
	{0, 1, 2, 3}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a; cin >> a;
		cnt[a]++;
	}

	for (int j = 0; j < 4; ++j) {
		for (int i = 0; i < 4; ++i) {
			if (!cnt[i]) continue;
			int can = min(cnt[i], cnt[prio[i][j]]);
			ans += (i ^ prio[i][j]) * can;
			cnt[i] -= can;
			cnt[prio[i][j]] -= can;
		}
	}
	cout << ans;
}