달팽이 귀엽
-
[Dev-Ping9] 백준 2869번 - 달팽이는 올라가고 싶다 (Java)코딩테스트/백준 2021. 11. 16. 12:45
# 문제 설명 달팽이가 귀엽다... 미끄러진다니... 시간제한 0.15 초 이므로 Brute-Force로는 못품 (for문을 돌리는 순간 통과 안될 것) 규칙을 찾자! 이왕이면 식으로 바로 구할 수 있어야 0.15초를 뚫을 것이다. # 규칙 (식) 하루동안 달팽이가 올라가고 미끄러진 높이는 A-B (달팽이의 속력) 정상에 올라서면 -B 가 발생하지 않음 (딱 한번만 B가 제외된다는 뜻) 그럼 올라갈 나무 높이에서 미리 -B를 해주면 됨 (미끄러졌다는 건 올라갈 나무높이가 더 길어졌다는 건데, 더 짧게 만들어주는 것) day = (tree-B) / (A-B) 가 성립 (올림 처리를 해줘야 한다. 9미터를 4의 속도로 올라가면 3일이 걸리기 때문) 아래의 식으로도 유도 할 수 있다. // up = A-B(d..