hippohmh   6년 전

안녕하세요. 

1011번 문제를 풀면서 처음에 현재 코드에서 unsigned int 부분을  int로 했더니 시간초과가 떴습니다.

그런데 이 부분을 unsigned int로 사용하니까 시간초과가 해결되네요....ㅋㅋ 


왜 그럴까요??

djm03178   6년 전

이 문제 푼지 좀 돼서 잘 기억은 안 나는데, 저도 처음에 int로 했다가 틀렸습니다 떠서 unsigned int로 바꾸고 맞은 흔적이 있네요. 중간 단계에서 오버플로가 나나 봅니다. 다만 이 코드에서는 그게 무한루프로 빠져드는 경로가 있는 모양이고요.

pcgos1   6년 전

int 형은 4바이트인데, 음수까지 표현하기 때문에 2바이트 즉 16비트를 이용해서 양수를 표현합니다. 이것은 최댓값 2^16 까지 표현못합니다.

하지만 이 문제에서 입력값이 2^31까지 들어간다고 했으므로, 오버플로우가 발생해서 이상하게 동작할 수 있습니다. 

예를 들어, 최댓값을 넘어가서 거리가 음수가 될 수 있습니다.

unsigned int의 경우 4바이트로 양수만을 표현하므로 2^32까지 표현가능하기 때문에 정상동작합니다.

따라서 조금 더 큰 자료형을 사용하거나, unsigned int를 사용하시는게 올바른 것 같습니다.


pcgos1   6년 전

거리인 dist가 음수가 된다고 생각하니, while(1)에서 못빠져 나오는 것 같습니다.

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