목록달팽이는올라가고싶다 (1)

그림판유저의 은밀한 개발

[BOJ] 백준 2869 - 달팽이는 올라가고 싶다

백준 2869 - 달팽이는 올라가고 싶다 달팽이는 낮에 a 미터를 올라가고, 밤에 b미터 떨어집니다. (정상을 도달하는 순간 미끄러지지 않으므로, 끝나게 됩니다.) 이런 문제는 DP를 접근하는 것과 같이 작은 문제부터 생각해야 합니다. 먼저, 달팽이는 하루가 지난 다음날 아래와 같이 이동한 것을 알 수 있습니다. 즉, 1일이 지날 때마다 a - b 만큼을 이동하게 됩니다.일반적으로, 1일에 a - b 만큼을 이동한다는 식을 찾게되면, n * (a - b) >= v 인 n 을 찾으려는 오류를 범하게 됩니다. 여기서 주의할 점은 정상을 도달하는 순간 미끄러지지 않는다는 점입니다. (n + 1)번째의 날에 나무 위에 도달한다고 가정한다면,n 번째 날이 지난 달팽이의 이동거리는 n * (a - b) 이게 되고,..
알고리즘/acmicpc[백준] 2019. 3. 7. 22:51
이전 Prev 1 Next 다음