[백준.11508-C언어] 2+1 세일

문제. 

KSG 편의점에서는 과일우유, 드링킹 요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다. 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다.

 

재현이는 KSG 편의점에서 친구들과 같이 먹을 총 N팩의 유제품을 구입하려고 합니다. 재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

 

입출력.

첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다. 두 번째 줄부터 N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어집니다. 재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 2^31-1보다 작거나 같다.

 

방법.

입력받은 유제품의 가격을 내림차순으로 정리하고, 모든 유제품 가격의 합을 구한다. 그리고 3n번째의 값을 합에서 빼준다. (아래 코드는 시간 초과된 코드..)

#include <stdio.h>

void sort(int size, int *arr); //정렬
int find_min(int size, int *arr, int sum); //최소비용 반환

int main(void){
    //입력
    int size, sum=0;
    scanf("%d", &size);
    int arr[size];
    for(int i=0; i<size; i++){
        scanf("%d", &arr[i]);
        sum+=arr[i];
    }

    //정렬
    sort(size, arr);
    //최소비용찾기 + 출력
    printf("%d", find_min(size, arr, sum));

    return 0;
}

void sort(int size, int *arr){
    int temp;
    for(int i=0; i<size-1; i++){
        for(int j=i; j<size; j++){
            if(arr[i]<=arr[j]){
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }
}

int find_min(int size, int *arr, int sum){
    for(int i=2; i<size; i+=3){
        sum-=arr[i];
    }
    return sum;
}

 

Insight.

1. 정렬해서 전체 합을 구하고 3n번째 값을 빼려고 하니 시간 초과 발생

2. 반복문을 많이 썼나 싶어서 , 입력을 받을 때 아예 합을 구했다. 그리고 3n번째 빼기... 또 시간 초과!

3. 시간 초과로 계속 잘못된 답안이라고 해서 얼마나 시간 초과된 건가 싶어서 결국 실행 시간을 측정하는 방법까지 찾아봤다.

 

 

Clang 실행 시간 측정하기

<time.h> 헤더 파일에 속한 clock함수를 사용한다. 시작 시간과 끝 시간을 저장하고, 차이를 구하면 실행시간이 된다. 사용법은 아래와 같다.

#include <stdio.h>
#include <time.h>
 
int main() {    
  //시간 측정에 필요한 변수 선언
  clock_t start, end;
  double result;

  start = clock(); //시간 측정 시작

  //시간 측정을 원하는 명령문

  end = clock(); //시간 측정 끝

  //끝 시간 - 시작 시간 = 총 실행시간
  result = (double)(end - start);
  //초 단위로 나오게하기위해 CLOCKS_PER_SEC로 나누어줌
  printf("실행 시간 : %f", result/CLOCKS_PER_SEC);
  
  
  return 0;
}

입력을 받는 시간이 짧으면 1초 이내로 결과를 반환하지만 아닌 경우는 1초를 넘어서 계속 시간 초과였나.. 다른 정렬방법을 사용해보거나 해야 할 거 같은데 이 외의 방법은 떠오르는 게 없어서 이 문제는 좀 더 고민해봐야겠다.

 

 

 

 

11508번: 2+1 세일