17976번 - Thread Knots
음 간단한 문제라 생각했는데 96퍼에서 계속 틀리네여... 어디서 예외처리를 안한건지 아니면 코드자체가 방향이 틀린건지 모르겠네여 주석은 열심히 달았습니다. 한 번 읽어보시고 반례나 지적할 부분 있다면 해주세요
MAX의 값이 과연 충분할까요?
아! 충분하지 않네요 .. 그런데 MAX의 범위를 충분치 바꾸었는데 이번에는 시간초과가 나네요..
맥스만 바꾸면 mid를 계산할 때 오버플로우가 납니다.
오버플로우가 난다는 게 무슨 뜻인가요..?
코드는 r값에 MAX값을 2147483647로만 수정한 것입니다.
l이 10억이고 r이 MAX이면 l+r은 int가 표현할 수 있는 범위를 벗어납니다. 그러니 mid 역시 올바른 값을 가지지 못합니다.
하 결국 변수타입 문제이군요.. 정말 정말 감사합니다. 그런데 혹시 변수 타입이 제대로 설정되지 않은 경우 왜 시간초과가 발생하는지 알려주실 수 있나요..? 저는 시간초과의 원인은 반복문으로 인한 시간복잡도 증가밖에 없다고 생각했는데 그러지 않은가보네요
정확히 따져보지는 않았지만 mid가 잘못 계산되어 lo가 계속 올라가는 것이 반복되면 결국 lo도 MAX를 넘어서며 오버플로우가 되고, 그 때문에 lo가 hi보다 커지는 것이 아닌 오히려 음수로 가서 반복문이 계속 돌게 될 수 있어 보입니다.
그리고 오버플로우와 같은 undefined behavior는 무슨 결과를 일으켜도 원래 이상하지 않습니다. 전혀 예상하지 못한 방향으로 무한 루프에 빠지는 것도 충분히 가능합니다.
아아 감사합니다! 친절히 알려주셔서 큰 도움된 것 같습니다
댓글을 작성하려면 로그인해야 합니다.
q8514199 4년 전 1
음 간단한 문제라 생각했는데 96퍼에서 계속 틀리네여... 어디서 예외처리를 안한건지 아니면 코드자체가 방향이 틀린건지 모르겠네여 주석은 열심히 달았습니다. 한 번 읽어보시고 반례나 지적할 부분 있다면 해주세요