[NYPC 2021_예선문제] 파티

풀 때 약간 뇌를 빼고(?) 풀었던 문제다. 그냥 내키는 대로 코딩을 짜서 코드가 더러워 보일 가능성이 매우 높다. 우선 문제 전문은 다음과 같다:

돈을 동등하게 맞춰야하는 간단한 문제이다. 가장 간단한 방법은, 우선 모든 돈을 다 합친 후 n빵(?)을 한 후에, 쓴 돈이 n빵보다 크면 돈을 받고 n빵보다 작으면 돈을 주는 방법이다.

주의해야할 점은, 주는 돈 자체가 최소값이어야 한다는 점이다. 즉, 움직이는 돈이 가장 작아야 하므로, 돈을 받는 사람은 최대한 적게 받아야 한다는 것이다.

위 그림에서 예를 들어보자면, 우선 첫 번째 그림은 총 2667원의 돈이 움직였으며, A, B, C가 각각 쓴 돈은

A : 3333원
B : 3334원
C : 3333원

이 된다. 그러나 두 번째 그림은 2666원의 돈이 움직였으며, 각각 쓴 돈은

A : 3334원
B : 3333원
C : 3333원

이 된다. 가장 많은 돈을 쓴 사람이 결론적으로 많이 가지고 있어야, 돈이 가장 적게 움직인다는 것을 알 수 있다. 이를 코드로 표현하면

#include <stdio.h>
#include <stdlib.h>

void sorting(int*, int);

int main(void){
	int student;
	scanf("%d", &student);
	int* money = (int*)malloc(sizeof(int) * student);
	int sum = 0;
	for (int i = 0; i < student; i++) {
		scanf("%d", &money[i]);
		sum += money[i];
	}
	sorting(money, student);
	int devided_money = sum / student; int remain = sum % student;
	int* fair_money = (int*)malloc(sizeof(int) * student);
	for (int i = 0; i < student; i++) {
		fair_money[i] = devided_money;
	}
	if (remain == 1) {
		fair_money[0]++;
	}
	else if (remain == 2) {
		fair_money[0]++; fair_money[1]++;
	}
	int result = 0;
	for (int i = 0; i < student; i++) {
		if (money[i] < fair_money[i]) {
			result += fair_money[i] - money[i];
		}
	}
	printf("%d\n", result);
	free(money);
	free(fair_money);
	return 0;
}
void sorting(int* arr, int num) {
	for (int i = 0; i < num; i++) {
		for (int j = i; j < num; j++) {
			if (arr[i] < arr[j]) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

이러한 코드가 나온다. 이 코드 또한 테스트를 받지 않은 코드이므로, 정확하지 않을 가능성이 있다. 하나하나 살펴보도록 하자.

int* money = (int*)malloc(sizeof(int) * student);

우선 돈을 입력받기 위해, 동적 할당으로 배열을 하나 만들었다.

sorting(money, student);

void sorting(int* arr, int num) {
	for (int i = 0; i < num; i++) {
		for (int j = i; j < num; j++) {
			if (arr[i] < arr[j]) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

그리고 정렬을 한다. 정렬을 하는 이유는, 돈을 가장 많이 쓴 순서대로 정렬하여 1원씩 더 주기 위해서이다.

int devided_money = sum / student; int remain = sum % student;
int* fair_money = (int*)malloc(sizeof(int) * student);
for (int i = 0; i < student; i++) {
	fair_money[i] = devided_money;
}

우선 기본적으로 나눠져야할 돈이 devided_money 변수에 저장되고, remain에는 다 나눠지지 못한 돈들이 들어간다. fair_money를 동적 배열로 만든 뒤, devided_money에 저장한다.

if (remain == 1) {
	fair_money[0]++;
}
else if (remain == 2) {
	fair_money[0]++; fair_money[1]++;
}

나머지가 1인 경우, 맨 앞의 값에만 하나를 나눠주고, 나머지가 2이면 맨 앞의 값과 그 뒤의 값에 하나씩 나눠준다.

int result = 0;
for (int i = 0; i < student; i++) {
	if (money[i] < fair_money[i]) {
		result += fair_money[i] - money[i];
	}
}

result라는 새로운 변수를 선언한 후, 자기가 쓴 돈과 적절하게 분배되어야 할 돈을 크기 비교해 result에 더해준 뒤, result를 결과로서 출력하면 된다.

글을 쓰면서도 고치고 싶은 생각이 엄청 많이 든 코드이다. 대충 봐도 정말 못 짠 코드라는 것이 느껴진다. 혹시 이 글을 보는 사람이 있다면, 코드를 이렇게 짜지는 말도록 하자.