글 읽기 - 1715번 카드정렬하기 문제 시간초과가뜹니다.

monkeydluppy 9년 전 0

n개를 입력받으면

2n개를 동적할당 해주고

오름차순으로 정렬한 다음

앞의 두개의 합을 배열의 (n+k)-1인덱스에 넣어주고

그 두개를 제외한 것들과 그 두개의 합만 다시 오름차순으로 정렬하고.. 하는식으로 해서

섞는 수를 구했습니다.

처음엔 n개

그다음엔 n-1개

...

for문안에선 이런식으로 정렬합니다.

그런데 시간초과가 나서 난감합니다..

다른 자료구조나 알고리즘을 사용해야 하나요...?

#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
 
using namespace std;
 
int main()
{
    int *arr;
    int num_c;
    int i,j;
    int acc;
    int sum = 0;
    scanf("%d", &num_c);
 
    arr = (int*)malloc(sizeof(int)*num_c*2);
 
    for (i = 0; i < num_c; i++)
        scanf("%d", &arr[i]);
             
     
    sort(arr, arr + num_c);
     
   
    for (i = 0,j=0; i < num_c-1; i++,j=j+2)
    {
        acc = arr[j] + arr[j+1];
        sum += acc;
         
        arr[num_c + i] = acc;
        sort(arr+i+2, arr + num_c+i+1);
    }
 
    printf("%d\n", sum);
}

pichulia 9년 전 1

이런 경우엔 다른 자료구조를 사용해야겠네요....

std::priority_queue 에 대해 검색해보시길

h0ngjun7 9년 전 1

말씀하신 알고리즘 시간복잡도를 분석해보면 O(N^2 log N)가 나옵니다. (2개를 선택하는 게 N-1번, 정렬하는데 N log N. N이 1씩 줄어든다하더라도 중간값 N/2를 잡고 시간복잡도 계산을 하면 N^2 log N이 나오죠)

힙이나 우선순위 큐, binary indexed tree 등의 자료구조를 활용할 수 있습니다.

monkeydluppy 9년 전 0

감사합니다.

덕분에 우선순위큐를 이용해 풀었습니다.!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1715번 카드정렬하기 문제 시간초과가뜹니다.

monkeydluppy 9년 전 0

pichulia 9년 전 1

h0ngjun7 9년 전 1

monkeydluppy 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말