안녕하세요.
오늘은 백준 2869번: 달팽이는 올라가고 싶다(링크) 문제를 풀어보려고 합니다.
문제
땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
출력
첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.
예제 입력
2 1 5
5 1 6
100 99 1000000000
예제 출력
4
2
999999901
제한
시간 제한: 0.15초
- node.js: 0.25 초
- C# 6.0 (Mono): 0.25 초
- C# 3.0 (Mono): 0.25 초
- VB.NET 2.0 (Mono): 0.25 초
- VB.NET 4.0 (Mono): 0.25 초
메모리 제한: 128Mb
풀이
단순히 높이가 V미터 될 때까지 A미터 올라가고 B미터 올라가도록 구현할 수 있는데, 이렇게 하면 시간초과가 납니다.
제한조건에서 시간제한은 0.15초로, V가 최대 값인 10억이 들어오면 약 10억 번 연산하게 되어 0.15초를 훨씬 넘어갑니다.
따라서 이 문제는 올라가는 과정을 직접 구현하는 것이 아님을 알 수 있습니다.
그렇다면 어떻게 풀어야 할까요? 달팽이가 올라가는 과정을 살펴봅시다.
달팽이는 먼저 낮에 A미터만큼 올라가게 됩니다. 이후 2가지 경우로 나뉩니다.
1) 정상에 도달한 경우
더 이상 움직이지 않습니다.
2) 정상에 도달 못 한 경우
밤에 다시 B미터만큼 떨어지게 됩니다.
2)에서 다음 날이 되면 달팽이는 (A-B) 미터만큼 올라간 것과 똑같습니다. 즉, 매일 (A-B) 미터만큼 오르는 것과 같으므로 올라가는데 걸리는 날짜는 V/(A-B)를 떠올릴 수 있습니다.
그러나 1)의 경우처럼 낮에 움직여 정상에 도달한 경우 더 이상 미끄러지지 않으므로 A미터만큼 올라간 것이 됩니다.
이때 올라간 높이는
C = (A-B) + (A-B) + ... + (A-B) + A,
(C-B) = (A-B) + (A-B) + ... + (A-B) + (A-B)
즉, (C-B)높이인 나무를 매일 (A-B)만큼 오른 것과 같다고 볼 수 있습니다. 입력 값 V로 바꾸면
V = (A-B) + (A-B) + ... + (A-B) + K,
(V-B) = (A-B) + (A-B) + ... + (A-B) + (K-B)
따라서 막대 크기 V를 V-B로 바꾸어 매일 A-B미터만큼 오르는 문제로 바꾸면 걸린 날짜는 (V-B)/(A-B).
만약 (V-B)%(A-B)의 값이 0이 아니라면 아직 못 올라간 높이가 있고, 해당 높이는 A보다 작으므로 걸린 날짜에 1을 더해줍니다.
정답
#include <stdio.h>
int main()
{
long int a,b,v;
int count=0;
scanf("%ld %ld %ld", &a, &b, &v);
if((v-b)%(a-b) == 0)
{
count = (v-b)/(a-b);
}
else
{
count = (v-b)/(a-b) + 1;
}
printf("%d",count);
return 0;
}이렇게 해서 백준 2869번 달팽이는 올라가고 싶다 문제를 풀어보았습니다.
댓글로 질문을 남기시면 성실히 답해드리겠습니다
감사합니다!