SW 4050 재광이의 대량 할인 [D4]

처음에는 Insertion Sort로 정렬하였는대, 시간제한에 걸려서 Counting Sort로 구현하였습니다.

아래에 Insertion Sort 코드도 올려두었습니다.

//count sort사용

#include <stdio.h>

int T;

int count[100001] = { 0, };

int main()

{

scanf("%d", &T);;

for (int tc = 1; tc <= T; tc++){

unsigned long long sum = 0;

int N, input, tmp = 0, max = 0;;

scanf("%d", &N);

for (int i = 0; i < N; i++){

scanf("%d", &input);

max = max > input ? max : input;

count[input]++;

}

//큰 순서대로 3번째 값은 더하지 않는다.

int cnt = 0;

for (int i = max; i >= 0;){

if (count[i] != 0){

count[i]--;

if (cnt == 2){

cnt = 0;

}

else{

sum += i;

cnt++;

}

}

else{

i--;

}

}

printf("#%d %lld\n", tc, sum);

}

return 0;

}

Insertion Sort로 구현한 것

#include <stdio.h>

int T;

int arr[100001] = { 0, };

//1<=N <=100,000

//1 <= ci <= 100,000

void insertionSort(int N)

{

int value = 0, j;

for (int i = 1; i < N; i++){

if (arr[i] >= arr[i - 1]){ continue; }

else{

value = arr[i];

for (j = i - 1; arr[j] > value; --j){

arr[j + 1] = arr[j];

}

arr[j + 1] = value;

}

}

}

int main()

{

scanf("%d", &T);;

for (int tc = 1; tc <= T; tc++){

int N, input, tmp=0;

unsigned long long sum = 0;

scanf("%d", &N);

for (int i = 0; i < N; i++)

scanf("%d", &arr[i]);

insertionSort(N);

int cnt = 0;

for (int i = N-1; i >=0; i--){

if (cnt == 2){

cnt = 0;

}

else{

cnt++;

sum += arr[i];

}

}

printf("#%d %lld\n", tc, sum);

}

return 0;

}