공부하는 개발자 핑구 🐧 공부하는 개발자 핑구 🐧

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

# Description # 어떤 접근 방법이 좋을까? 1. 문제의 답은 최적의 해를 구하는 것 2. 이전의 해를 이용하여, 지금의 해를 구할 수 있는가? (부분 구조가 성립하는가? => Yes) => 1번과 2번 문항을 통해 DP를 적용 시킬 수 있다는 근거를 가지게 되었다. 3. 단순무식하게 풀었을 때 연산량이 많은가? f(a) 를 a 부터 시작한 [연속합2] 의 최대라 정의 했을때, => 1~N , 2~N , 3~N, .... , N~N => O(N^2) 4. 공간의 제약이 많은가, 시간의 제약이 많은가 => Description을 보면, 확실히 시간의 제약이 많다. (시간제한 및 n의 최대값) => 보통 1초에 1억번 연산가능 (N^2 이면, N=100_000일때, 1천억번 연산해야함 => 1천초..