글 읽기 - 이거 더빠른 알고리즘 없나요??

zmfkdyd 8년 전 0

도와주세여ㅠㅠ

자기자신이랑 중복제외하고 비교하는거 해봤는대 시간초과네요

#include<stdio.h>
#include<stdlib.h>
 
int main()
{
    int N, num, sum=0;
    int *liquid;
    int i, j;
    int minimum, check = 0,mini1,mini2;
    //  최솟값   
 
    scanf("%d", &N);
    {
        liquid = (int*)malloc(sizeof(int)*N);
        for (i = 0; i < N; i++)
        {
            scanf("%d", &liquid[i]);
        }
         
        for (i = 0; i < N; i++)
        {
            for (j = i+1; j < N; j++)
            {
                sum = liquid[i] + liquid[j];
                if (sum<0)
                {
                    sum *= -1;
                }
 
                if (check == 0)
                {
                    minimum = sum;
                    mini1 = liquid[i];
                    mini2 = liquid[j];
                    check = 1;
                }
                else if (minimum > sum)
                {
                    minimum = sum;
                    mini1 = liquid[i];
                    mini2 = liquid[j];
                }
            }
        }
 
        printf("%d %d", mini1, mini2);
    }

h0ngjun7 8년 전 0

정렬하고 이분탐색으로 비교하세요~

zmfkdyd 8년 전 0

정렬하는게 더 시간 오래걸리지 않을까요 하나하나 다 비교해야되니깐..

h0ngjun7 8년 전 0

힙 정렬이나 합병정렬을 사용하면 O(N log N)이 보장됩니다.

zmfkdyd 8년 전 0

한가지 더물어볼께 있는데요..

두액체끼리 더하는값을 일단 구해야 돼잖아요

더하는값을 구할때 만약 숫자가 5개있다고 하면 중복피해서

첫번째는 4번 더하고 두번째는 3 세번째 2 네번째 1 다섯번째 0 마지막이니깐...

근데 저렇게 저가말한대로 구할때 최솟값까지 같이 구해버리는게 훨씬 빠를것같기도한대 ㅠㅠ

shawn050912 6년 전 0

반례입니다.

그렇게 되면 절댓값이 가장 작은 수들만 더하여

-999 1 2

이렇게 있으면 원래는

1 2

가 출력되어야 하지만

위 알고리즘으로는 -999 1

이 출력되기 때문입니다.

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

문제

문제

출처

ICPC

이거 더빠른 알고리즘 없나요??

zmfkdyd 8년 전 0

h0ngjun7 8년 전 0

zmfkdyd 8년 전 0

h0ngjun7 8년 전 0

zmfkdyd 8년 전 0

shawn050912 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말