[백준/2869번] 달팽이는 올라가고 싶다 [Java]

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.15 초	128 MB	27957	6773	5655	28.354%

 

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

---

풀이

처음 문제를 접했을 때, 굉장히 쉬운 문제로 생각하고 접근했다. 실제로 구동환경에서도 잘 실행되었다. 근데 결과는 처참히 시간초과...

반복문을 사용하면 시간이 여지없이 초과되는 문제였다. 이는 문제에 대한 조건과 규칙을 이해하고 그에 따른 알고리즘을 세워야 통과되는 문제인것이다. 처음에는 while 문을 통해서 결과가 도출될 때까지 루프문을 돌렸는데, 이렇게 하면 통과가 되지 않는다...그래서 생각해 보았다. 결국 도달해야 하는 값에서 하루에 전진하는 거리를 나눠준다면?? 그렇다면 도달해야하는 값은 무엇인가? v라고 생각할 수도있지만 v에서 다시 내려가는 b값을 빼줘야 최대 하루 도달거리가 나온다. 그렇기 때문에 하루 전진하는 값 a-b를 v-b에서 나눠준다면 며칠 소요되는지 나오는 것이다. 근데 예외도 있다.만약에 이 결과가 0으로 나누어 떨어지지 않는다면 하루 더 소요해야 하는 점이다. 이를 if문으로 분류해 하루를 더해주고 출력해주면 끝! 조금 생각이 필요한 문제였다.ㅇㅅㅇ

import java.util.*;
 
class Main {
    public static void main(String[] args) {
            Scanner sc =new Scanner(System.in);
            long a=sc.nextInt();
            long b=sc.nextInt();
            long v=sc.nextInt();
            
            long temp=(v-b)/(a-b);
            if((v-b)%(a-b)!=0) {
                temp++;
            }
        System.out.println(temp);
            }
}
 

 

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다