글 읽기 - 세 용액

onjo0127 8년 전 3

초등부 용액 문제에 for문하나 더 씌워서 해 봤는데

40%대에서 틀리네요

정렬해놓고 절대값이 작아지는 쪽을 좁히며 최소값을 구하는 방식입니다.

#include <stdio.h>
#include <algorithm>
long long mn = 3000000009;
int arr[5009];

long long f(long long a)
{
    if(a<0)return -a;
    return a;
}

int main()
{
    int n,i;
    int a[3];
    int left,right;
    scanf("%d",&n);

    for(i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }

    std::sort(arr,arr+n);

    for(i=0;i<n;i++) {
        left=0;
        right=n-1;

        while(left!=right) {
            if(i != left && i != right) { //서로 다른 용액이어야 함
                if(mn > f(arr[left] + arr[right] + arr[i])) {
                    mn = f(arr[left] + arr[right] + arr[i]);
                    a[0] = arr[left];
                    a[1] = arr[right];
                    a[2] = arr[i];
                }
            }

            if(f(arr[left+1] + arr[right] + arr[i]) >= f(arr[left] + arr[right-1] + arr[i])) { // 절대값이 더 작아지는 쪽을 선택
                right--;
            }

            else {
                left++;
            }
        }
    }

    std::sort(a,a+3);

    printf("%d %d %d",a[0],a[1],a[2]);

    return 0;
}

koosaga 8년 전 2

f(arr[left] + arr[right] + arr[i])

여기서 int + int + int 라서 오버플로우가 나겠네요.

이게 문제인지는 잘 모르겠다만..

onjo0127 8년 전 0

그래서 함수도 long long형으로 만들었는데요...

indioindio 8년 전 2

인자가 long long이어도 int의 덧셈이 먼저 된 후에 long long으로 타입변환이 돼서 오버플로우는 여전히 일어날 것 같습니다.

onjo0127 8년 전 0

아하...

좋은 정보 감사합니다!

onjo0127 8년 전 0

질문 하나만 더 드릴게요...

이렇게 해도 틀리는데

형변환 이렇게 하는 거 맞나요?

#include <stdio.h>
#include <algorithm>
long long mn = 3000000009;
int arr[5009];

long long f(long long a)
{
    if(a<0)return -a;
    return a;
}

int main()
{
    int n,i;
    int a[3];
    int left,right;
    scanf("%d",&n);

    for(i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }

    std::sort(arr,arr+n);

    for(i=0;i<n;i++) {
        left=0;
        right=n-1;

        while(left!=right) {
            if(i != left && i != right) {
                if(mn>f((long long)(arr[left] + arr[right] + arr[i]))) {
                    mn = f((long long)(arr[left] + arr[right] + arr[i]));
                    a[0] = arr[left];
                    a[1] = arr[right];
                    a[2] = arr[i];
                }
            }

            if(f((long long)(arr[left+1] + arr[right] + arr[i])) >= f((long long)(arr[left] + arr[right-1] + arr[i]))) {
                right--;
            }

            else {
                left++;
            }
        }
    }

    std::sort(a,a+3);

    printf("%d %d %d",a[0],a[1],a[2]);

    return 0;
}

onjo0127 8년 전 1

아...

두 번째 괄호 없애니까 맞네요

모두 감사드립니다!

indioindio 8년 전 1

음 이렇게 하시는 건 사실 아까와 별반 차이가 없을 것 같습니다.

이 경우에도 여전히 arr[left] + arr[right-1] + arr[i] 의 덧셈이 완료된 후에 long long으로 변환되기 때문입니다.

arr를 long long형으로 선언하시거나, (long long) arr[left] + arr[right-1] + arr[i]로 덧셈하기 전에 셋 중 하나의 타입을 바꿔주시면

계산을 할 때 정보의 손실이 없는 쪽으로 형변환을 하기 때문에 오버플로우가 없는 결과를 얻을 수 있을 것 같네요.

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

문제

문제

출처

ICPC

세 용액

onjo0127 8년 전 3

koosaga 8년 전 2

onjo0127 8년 전 0

indioindio 8년 전 2

onjo0127 8년 전 0

onjo0127 8년 전 0

onjo0127 8년 전 1

indioindio 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말