애초에 if(sum_plus > LLONG_MAX - buf) 부분 검사하는 위치가 잘못되었습니다.
이미 sum_plus가 LLONG_MAX를 넘어간 순간부터 쓰레기값이므로,
그 이후로는 체크의 의미가 없습니다.
현재 로직으로는 더하기 전 체크가 아니라, 이미 더해진걸 체크하는거니까용
1247번 - 부호
생각해보니 애초에 LLONG_MIN이 절대값이 1이 더 크군욬ㅋㅋㅋㅋ
---
위에 제가 말한건 너무 대충본것같아요.. 죄송해요. 심지어 생각해보니 어차피 넘나들어서 쓰고 오버플로우 횟수를 기록한다면 쓰레기값도 아니네요;;
애초에 검사 로직 빼고 그냥 더하고 오버플로우 횟수 구하셔도 될것같아요.
그동안 전 오버플로우를 오히려 이용해서 풀어본적이 없다보니 ㅠㅠ
죄송합니다.
---
게시판에서 취미로(?) 수많은 반례들을 찾아봤는데..
이게 남의 코드면 대강 틀렸겠거니 하는 부분 후벼파면 나오는데
저도 제 코드 반례는 잘 못찾습니다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
해당 부분은 당연히 맞겠다고 생각하고 넘어가게되서요 사람 심리가.
그래도 남의꺼 찾다보면 한 90%정도는
문제에 제시된 limit의 중앙부분보단 딱 limit 걸친부분으로 계속 시도해보면 나올때가 많더라구요.
엌ㅋㅋㅋㅋ
일단 위 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; }
검사 로직 없이 overflow를 구하면 문제가 long long 범위가 초과 되어버리지 않나요?
-> 네네 결국 초과되서 쓰레기값이 되긴한데, 이 쓰레기값이 결국 '부호'만 정하는대는 문제가 없다는걸 간과했어요.
그리고 보통 일부러 오버플로우나 언더플로우 내서 풀 경우가 잘 없다보니 (파이썬이나 자바의 경우 특히.. 무한 정수 표현이 가능해서요)
무의식적으로 이걸 어케 활용하지 했는데,
결국 오버플로우 언더플로우를 원형 배열쯤으로 보셔도 되거든요.
그러니까 음.. 만약에 최대값이 3, 최소값이 -4라면
0 1 2 3 -4 -3 -2 -1
요게 원형으로요! 3에서 오버플로우나면, 즉 3에서 1 더하면 -4가 되는거구요.
-4에서 언더플로우나면 3이 되는거구요.
그러니 오버플로우, 언더플로우 횟수만 알면 합 자체는 쓰레기값이지만, 부호는 알 수 있는거죠.
댓글을 작성하려면 로그인해야 합니다.
sc3289 3년 전
채점 진행 중 30% 넘어가면서 틀렸다고 나오는데 문제가 뭔지 모르겠습니다.
채점 중에 시간초과도 아니고 저렇게 뜨면 반례가 있다는 거 아닌가요?
아무리 찾아봐도 반례를 못찾겠습니다.
사용한 풀이법은 over_flow 횟수를 부호별로 count하여 진행했습니다.
자료형에 잘 담길 수 있도록 수 크기는 최솟값, 최댓값을 빼주면서 조절했습니다.
어디가 틀린걸까요?