인프런 커뮤니티 질문&답변
작성한 질문수
6 - J 놀이공원 문제 질문있습니다
작성
·
347
0
안녕하세요 큰돌 강사님
놀이공원 문제를 풀다가 맞왜틀엘 빠져서 한참 고민하다 이분탐색의 hi 최댓값을 1e18로 잡은게 원인임을 찾았고 600억으로 바꾸니 정답처리 되는것 까지 확인했습니다.
강사님께서는 600억을 잡으셨고 그 이유도 이해를 했는데 1e18로 잡았을때 시간초과가 났더라면 이분탐색의 연산 횟수가 늘어서 그랬는지 분석을 해봤을텐데 "틀렸습니다"가 나와버리니 그 이유를 모르겠습니다.
이분 탐색에서 범위가 커진것이 왜 오답 처리가 된 것인지 그 이유가 궁금합니다.
1e18로 잡아서 틀린 오답코드
http://boj.kr/475081ce3a674e36b5f5941ddcd85484
600억으로 바꿔서 맞은 정답코드
http://boj.kr/9f9ba12d52124483a6b73384541c159f
답변 1
1
안녕하세요 aass님 ㅎㅎ
일단 보통은 1e18해도 맞는 문제도 많습니다.
1e18은 이 문제의 범위 밖에서 연산을 수행할 수 있습니다. 이 문제의 정답이 될 수도 있는 범위는 600억입니다.그렇기 때문에 600억안에서 하면 문제의 범위 안에서 연산을 수행하죠. 다만, 1e18을 하게 되면 수가 너무나 크고 그 부분부터 시작해서 문제의 답 범위 밖에서 연산을 수행하게 됩니다.
그러나, 1e8에서 문제의 답의 범위안에 들어오는데 그렇게 많은 시간이 걸리지 않습니다. 그래서 보통은 맞습니다만, 제가 모르는 반례가 있는 거 같습니다. 저도 좀 더 살펴보겠습니다.
일단은 "원래는 long long일경우에는 1e18로 하면 대강 맞으나 문제의 최대범위를 보고 최대값을 잡는게 정확하다."라고 생각하고 넘어가시는게 좋을 거 같습니다.
제가 디버깅했던 코드는 다음과 같습니다. M이 100까지 해봤는데요.
2000000000 100
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
#define INF 1e18
MID : 500000000000000000
MID : 249999999999999999
MID : 124999999999999999
MID : 62499999999999999
MID : 31249999999999999
MID : 15624999999999999
MID : 7812499999999999
MID : 3906249999999999
MID : 1953124999999999
MID : 976562499999999
MID : 488281249999999
MID : 244140624999999
MID : 122070312499999
MID : 61035156249999
MID : 30517578124999
MID : 15258789062499
MID : 7629394531249
MID : 3814697265624
MID : 1907348632811
MID : 953674316405
MID : 476837158202
MID : 238418579100
MID : 119209289549
MID : 59604644774
MID : 29802322386
MID : 14901161192
MID : 7450580595
MID : 3725290297
MID : 1862645148
MID : 931322573
MID : 465661286
MID : 698491929
MID : 582076607
MID : 640284268
MID : 611180437
MID : 596628522
MID : 603904479
MID : 600266500
MID : 598447511
MID : 599357005
MID : 599811752
MID : 600039126
MID : 599925439
MID : 599982282
MID : 600010704
MID : 599996493
MID : 600003598
MID : 600000045
MID : 599998269
MID : 599999157
MID : 599999601
MID : 599999823
MID : 599999934
MID : 599999989
MID : 599999961
MID : 599999975
MID : 599999968
MID : 599999971
MID : 599999969
MID : 599999970
100
#define INF 60000000004
MID : 30000000002
MID : 15000000000
MID : 7499999999
MID : 3749999999
MID : 1874999999
MID : 937499999
MID : 468749999
MID : 703124999
MID : 585937499
MID : 644531249
MID : 615234374
MID : 600585936
MID : 593261717
MID : 596923826
MID : 598754881
MID : 599670408
MID : 600128172
MID : 599899290
MID : 600013731
MID : 599956510
MID : 599985120
MID : 599999425
MID : 600006578
MID : 600003001
MID : 600001213
MID : 600000319
MID : 599999872
MID : 600000095
MID : 599999983
MID : 599999927
MID : 599999955
MID : 599999969
MID : 599999976
MID : 599999972
MID : 599999970
100
감사합니다.