surung9898   3년 전

최근 코드포스에 관련 문제가 출제되었더라구요... 그래서 연습 겸 Prefix Sum을 이용해 풀어보려 했는데 4%에서 WA 받았습니다...

계산 상 long long int를 쓰면 딱히 자료형 쪽으로 문제가 생길 것 같지도 않고, 이와 유형이 유사한 10986(https://www.acmicpc.net/problem/10986)에서는 매우 유사한 알고리즘으로 정답을 받았었는데다, 넣어본 몇몇 케이스에서도 올바르게 출력하는 것을 보아 어떤 코너케이스 같은게 있지 않을까 추측해보았는데요.... 제가 무지하여 어떤 부분에서 오류가 있는지 잘 모르겠습니다...

부디 반례나, 알고리즘 상의 오류를 찾아주시면 감사하겠습니다...

yj10516   3년 전

k와 for 반복문 안의 i가 모두 int형이라 43번째줄의 tmp2를 계산하실때 오버플로우가 있을 수 있습니다.

skeep194   3년 전

3 1000000000

1000000000 1000000000 1000000000

correct answer: 6

your answer: 3

k*(i+1) 에서 k도 int형이고 i+1도 int형이라 중간 계산과정 오버플로우 가능합니다.

surung9898   3년 전

두 분 다 감사합니다! 제가 멍청했습니다... 제가 별도로 체크했던 테스트케이스에서는 10억 대신 1억을 넣는 바람에 미처 찾질 못했었네요...

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