sc3289   1년 전

채점 진행 중 30% 넘어가면서 틀렸다고 나오는데 문제가 뭔지 모르겠습니다.

채점 중에 시간초과도 아니고 저렇게 뜨면 반례가 있다는 거 아닌가요?

아무리 찾아봐도 반례를 못찾겠습니다.

사용한 풀이법은 over_flow 횟수를 부호별로 count하여 진행했습니다.

자료형에 잘 담길 수 있도록 수 크기는 최솟값, 최댓값을 빼주면서 조절했습니다.

어디가 틀린걸까요?

nahwasa   1년 전

애초에 if(sum_plus > LLONG_MAX - buf) 부분 검사하는 위치가 잘못되었습니다.

이미 sum_plus가 LLONG_MAX를 넘어간 순간부터 쓰레기값이므로,

그 이후로는 체크의 의미가 없습니다.

현재 로직으로는 더하기 전 체크가 아니라, 이미 더해진걸 체크하는거니까용

sc3289   1년 전

sum_plus + buf 를 해야 LLONG_MAX를 넘어간 상황이고

이건 덧셈 결과를 도출하기 전에

sum_plus > LLONG_MAX - buf 이 부분으로 덧셈 연산을 하면 overflow가 일어나는지 안일어나는지 확인하는 부분 아닌가요?

sc3289   1년 전

아무리 봐도 더하기 전 체크가 맞습니다...

실제로 overflow가 일어나는 상황인 예제도 잘 나오고 있습니다.

반례가 도통 뭔지 잘 모르겠습니다 ㅜㅜ

nahwasa   1년 전

//buf<0 부분에서 sum_minus = sum_minus - LLONG_MIN + buf;

이게 잘못되지 않았나싶어요

아래와 같은 경우 + 부호가 나오네요.

4
9223372036854775807
-9223372036854775807
9223372036854775807
-9223372036854775807

sc3289   1년 전

그러네요....

혹시 이런 반례는 그냥 이것저것 경우의 수 생각하면서 떠올려야 하는건가요?

매 문제마다 input 생각해보는게 쉽지가 않네요

nahwasa   1년 전

생각해보니 애초에 LLONG_MIN이 절대값이 1이 더 크군욬ㅋㅋㅋㅋ

---

위에 제가 말한건 너무 대충본것같아요.. 죄송해요. 심지어 생각해보니 어차피 넘나들어서 쓰고 오버플로우 횟수를 기록한다면 쓰레기값도 아니네요;;

애초에 검사 로직 빼고 그냥 더하고 오버플로우 횟수 구하셔도 될것같아요.

그동안 전 오버플로우를 오히려 이용해서 풀어본적이 없다보니 ㅠㅠ

죄송합니다.

---
게시판에서 취미로(?) 수많은 반례들을 찾아봤는데..

이게 남의 코드면 대강 틀렸겠거니 하는 부분 후벼파면 나오는데

저도 제 코드 반례는 잘 못찾습니다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

해당 부분은 당연히 맞겠다고 생각하고 넘어가게되서요 사람 심리가.

그래도 남의꺼 찾다보면 한 90%정도는

문제에 제시된 limit의 중앙부분보단 딱 limit 걸친부분으로 계속 시도해보면 나올때가 많더라구요.

sc3289   1년 전

아.. 방금 저도 여기저기 값 print 해보면서 절대값 다른거 찾았네요.........

검사 로직 없이 overflow를 구하면 문제가  long long 범위가 초과 되어버리지 않나요?

sc3289   1년 전

근데 이게 저는 LLONG_MAX가 절대값이 더 큽니다.

뭐 어찌어찌 하다보면 계속 절대값이 변하네요?

nahwasa   1년 전

엌ㅋㅋㅋㅋ

일단 위 sc3289님 코드 기반으로 위에 제가 말한대로 일부러 오버플로우 내는 방식으로 한번 바꿔서 AC 성공했습니다!

다른 언어들도 하긴하지만 아무래도 알고리즘 메인으로 쓰는게 자바다보니 오버플로우를 활용할 생각자체를 못했었는데,

저도 마인드적으로 새로운걸 얻어가네요.. 감사합니다.

#include <stdio.h>
#include <limits.h>

int main()
{
    int n,over_plus = 0, over_minus = 0;
    long long buf, sum, b_sum;
    for(int j = 0;j<3;j++)
    {
        scanf("%d",&n);
        over_plus = 0;
        over_minus = 0;
        sum = 0;
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&buf);
            b_sum = sum;
            sum += buf;
            if (b_sum > 0 && sum < 0 && buf > 0)
                over_plus++;
            else if (b_sum < 0 && sum > 0 && buf < 0)
                over_minus++;
        }
        // print part
        if(over_plus == over_minus)
        {
            if (sum == 0)
                printf("0\n");
            else
                printf(sum > 0 ? "+\n" : "-\n");
        } else {
            if(over_plus > over_minus)
                printf("+\n");
            else
                printf("-\n");
        }
    }
    return 0;
}

sc3289   1년 전

절대값이 변하는거 때문에 코드에서 아예 범위를 제한해줬네요

overflow나면 부호 바꿔서 올라가는걸로 그냥 풀껄... 괜히 복잡하다고 생각하기 쉽게 하려다가 더 꼬였네요

MAX랑 MIN 값을 LLONG_MAX 안쓰고 다시 define해서 풀었더니 맞았네요 ㅎㅎ

감사합니다

overflow랑 MAX , MIN 절대값 공부 제대로 하네요 ㅋㅋㅋ

nahwasa   1년 전

검사 로직 없이 overflow를 구하면 문제가 long long 범위가 초과 되어버리지 않나요?

-> 네네 결국 초과되서 쓰레기값이 되긴한데, 이 쓰레기값이 결국 '부호'만 정하는대는 문제가 없다는걸 간과했어요.


그리고 보통 일부러 오버플로우나 언더플로우 내서 풀 경우가 잘 없다보니 (파이썬이나 자바의 경우 특히.. 무한 정수 표현이 가능해서요)

무의식적으로 이걸 어케 활용하지 했는데,

결국 오버플로우 언더플로우를 원형 배열쯤으로 보셔도 되거든요.

그러니까 음.. 만약에 최대값이 3, 최소값이 -4라면

0 1 2 3 -4 -3 -2 -1 


요게 원형으로요! 3에서 오버플로우나면, 즉 3에서 1 더하면 -4가 되는거구요.

-4에서 언더플로우나면 3이 되는거구요.

그러니 오버플로우, 언더플로우 횟수만 알면 합 자체는 쓰레기값이지만, 부호는 알 수 있는거죠.

sc3289   1년 전

아.......... 그러네요

쓰레기값은 만들어지면 안돼!

라는 강박이 이렇게 발목을 잡을 줄은.....

감사합니다 ㅎㅎ 많이 배워가네요

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