출처
- https://www.swexpertacademy.com
난이도
- 하 – 중 – (상) – 최상 – 풀지 못함
문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)
- 물건의 종류를 주고 각 물건의 값어치를 Input으로 준다. 주어진 물건을 3개의 그룹으로 나누어서, 모든 그룹에 속한 물건 값어치 합이 똑같아지는 답을 찾는 문제이다.
- SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 상세히 문제를 설명하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.
후기
- 처음 문제를 읽고는 정말 어렵지 않을 것 같았다. 단순히 전체 값어치의 합을 3으로 나누어서 그룹 2개를 만들면 하나가 같아질 거라고 판단했다. 그래서 findSub Recursive 함수를 만들어서 그룹 3개를 생성하였다. 하지만, 단순히 findSub으로 값어치의 합이 1/3되는 부분을 찾게 되면 1개의 그룹은 항상 1/3 값어치를 가지는 그룹이 생성되는 반면 나머지 2개의 그룹은 같은 값어치를 가지는 그룹을 만들지 못하는 경우가 발생한다.
- 그래서 다음으로 진행한 방법이 Quick Sort를 사용하여 물건의 값어치가 큰 것부터 순서대로 정렬하였다. 그리고 findSub함수를 사용하여 값어치가 큰 것부터 물건의 그룹을 나뉘도록 코드를 구현하였다. 큰 값어치부터 정렬을 하다 보면 3개의 그룹으로 나뉠 때 작은 값어치를 가진 물건으로 인해서 정확하게 3그룹으로 나누지 못하는 문제를 해결할 수 있었다.
코드
- Quick Sort 함수를 사용하여 값어치를 정렬 후 Recursive 함수를 사용하여 Group을 3개로 나누는 코드
- 실행 시간: 89ms (제일 빠른 코드 대비 대략 10% (81ms) 느림. Quick Sort 대신 Priority Queue를 사용해 보았는데 3ms 정도 성능향상이 있음)
#include <stdio.h>
//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable: 4996)
#define MAXSIZE 2000
typedef unsigned int ui;
ui inputSize;
ui input[MAXSIZE];
ui totalSum;
ui answer[3][MAXSIZE];
ui tCnt[3];
ui sum[3];
int visited[MAXSIZE];
//MK: visited List을 초기화 하는 부분. 각 물건이 어느 그룹에 속하는지를 알려줌
void init() {
for (int i = 0; i < inputSize; i++) {
visited[i] = -1;
}
}
//MK: Quick Sort를 진행하여서 값어치가 큰 것부터 정렬함
void quickSort(int begin, int end) {
int ptr = begin;
int i = begin;
int j = end;
if (begin >= end) {
return;
}
while (i < j) {
while (input[ptr] <= input[i] && i <= end) {
i++;
}
while (input[ptr] > input[j]) {
j--;
}
if (i < j) {
ui tmp = input[i];
input[i] = input[j];
input[j] = tmp;
}
}
ui tmp = input[ptr];
input[ptr] = input[j];
input[j] = tmp;
quickSort(begin, j - 1);
quickSort(j + 1, end);
}
//MK: 값어치의 합이 1/3되는 Group을 찾는 부분
int findSub(int id, int ptr, ui sum) {
if (sum == totalSum) {
return 1;
}
else if (sum > totalSum) {
return 0;
}
if (ptr == inputSize) {
return 0;
}
int ret = 0;
if (visited[ptr] == -1) {
visited[ptr] = id;
ret = findSub(id, ptr + 1, sum + input[ptr]);
if (ret == 1) {
return 1;
}
visited[ptr] = -1;
}
ret = findSub(id, ptr + 1, sum);
return ret;
}
int main() {
freopen("input.txt", "r", stdin);
int testCase = 0;
scanf("%d", &testCase);
for (int m = 0; m < testCase; m++) {
totalSum = 0;
scanf("%u", &inputSize);
for (ui i = 0; i < inputSize; i++) {
scanf("%d", &input[i]);
totalSum += input[i];
}
totalSum /= 3;
init();
//MK: Quick Sorting을 하여서 큰 수부터 작은 수로 정렬하는 부분
quickSort(0, inputSize - 1);
//MK: 2개의 Group의 동일한 값어치를 찾는 부분. 마지막 한 그룹은 자동으로 동일해짐
findSub(0, 0, 0);
findSub(1, 0, 0);
printf("#%d\n", m + 1);
for (int i = -1; i < 2; i++) {
for (int j = 0; j < inputSize; j++) {
if (visited[j] == i) {
printf("%u ", input[j]);
}
}
printf("\n");
}
}
return 0;
}