글 읽기 - 우왕 ㅠㅠ 계속 틀렸데요.. 반례가 뭐죠 ㅠㅠ

pcgos1 6년 전 0

계속 틀렸다고 뜨는데,, 머가 문제인지 잘모르겟어요...

혹시 틀린게 먼지만 한번 설명해주실분 ㅠㅠ

#include <cstdio>

void swap(unsigned int* a, unsigned int* b){
    unsigned int t = *a;
    *a = *b;
    *b = t;
}

void quickSort(unsigned int arr[], unsigned int left, unsigned int right) {
    unsigned int i = left, j = right;
    unsigned int pivot = arr[(left + right) / 2];

    do {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i<= j) {
            swap(&arr[i], &arr[j]);
            i++;
            j--;
        }
    } while (i<= j);
    
    /* recursion */
    if (left < j)
        quickSort(arr, left, j);
    
    if (i < right)
        quickSort(arr, i, right);
}

int main() {
    //전체 수 입력
    unsigned int N;
    scanf("%u", &N);
    
    //길이
    unsigned int K;
    scanf("%u", &K);
    
    unsigned int mid_order = (K+1)/2;
    unsigned int erase_last = K-mid_order;

    //입력
    
    unsigned int data[N];
    for(unsigned int i=0;i<N;i++){
        scanf("%u", &data[i]);
    }
    
    //정렬
    quickSort(data,0,N-1);
    
    //중앙값계산
    unsigned int sum=0;
    if(N==1){
        sum=data[0];
    }else {
        for(unsigned int i=mid_order-1;i<N-erase_last;i++){
            sum+=data[i];
        }
    }
    
    printf("%u\n",sum);
    
    return 0;
}

djm03178 6년 전 1

3 2

2 1 3

정답은 2입니다. 처음에 2 1에서 중앙값이 1이고, 그 다음에 1 3에서 중앙값이 1이기 때문이죠.

pcgos1 6년 전 0

감사합니다

pcgos1 6년 전 0

다시 수정해서 돌려봣는데, 먼가 2프로에서 틀렸어요. ㅠㅠ 가 뜹니다..

혹시 이거 푸신 분 중에서, 틀릴만한 반례같은거 아시는 분 있나요?

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    //입력 N, K
    unsigned int N, K;
    scanf("%u", &N);
    scanf("%u", &K);

    //입력
    unsigned int data[N];
    for(unsigned int i=0;i<N;i++){
        scanf("%u", &data[i]);
    }
    
    //
    unsigned int sum=0;
    for(unsigned int i=0;i<N-K+1;i++){
        vector<unsigned int> small_arr;

        //배열 분리
        for(unsigned int j=0;j<K;j++){
            small_arr.push_back(data[i+j]);
        }
        
        //분리된 배열 정렬
        sort(small_arr.begin(),small_arr.end());

        //중앙값 덧셈
        sum+=small_arr[((K+1)/2)-1];
    }
    
    //출력
    printf("%u\n",sum);
    
    return 0;
}

djm03178 6년 전 1

일단 답이 틀린 이유는 unsigned int로 모든 경우를 커버할 수 없어서입니다.

그런데 이건 long long을 쓰더라도, 시간초과가 날 알고리즘입니다. 루프를 O(N)번 돌면서 K개의 원소를 정렬하니 시간복잡도는 대략 O(N*KlgK)가 되겠죠. 최악의 경우 240억 정도 됩니다.

테케가 약해서인지 O(NK)로 짠 코드로 예전에 가까스로 통과시킨 적이 있었지만, 의도한 대로라면 O(NlgN)이나 O(NlgK) 시간에 푸는 알고리즘을 고려하셔야 합니다.

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

문제

문제

출처

ICPC

우왕 ㅠㅠ 계속 틀렸데요.. 반례가 뭐죠 ㅠㅠ

pcgos1 6년 전 0

djm03178 6년 전 1

pcgos1 6년 전 0

pcgos1 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말