2022.01.22 [백준] C# 달팽이는 올라가고 싶다

 

 

 

 

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2 1 5

예제 출력 1 복사

4

예제 입력 2 복사

5 1 6

예제 출력 2 복사

2

예제 입력 3 복사

100 99 1000000000

예제 출력 3 복사

999999901

---

using System;
class Program{
    static void Main(){
        string[] ss = Console.ReadLine().Split();
        int a = int.Parse(ss[0]);
        int b = int.Parse(ss[1]);
        int v = int.Parse(ss[2]);
        int n = 1;
        int h = 0;
        while(true){
            h+=a;
            if(h<v){
                h-=b;
            }else{
                Console.Write(n);
                break;
            }
            n++;
        }
    }
}

처음 while문을 이용해 문제를 풀었는데 시간 초과가 발생했다.

위 문제는 위 사진과 같이 시간 제한이 상수시간 O(1) 내로 풀어야 한다. 이렇게 하기 위해선 한줄 수식이나 이분탐색을 해야한다. 그래서 한줄 수식을 이용해서 코드를 작성했다.

---

using System;
class Program{
    static void Main(){
        string[] ss = Console.ReadLine().Split();
        int a = int.Parse(ss[0]);
        int b = int.Parse(ss[1]);
        int v = int.Parse(ss[2]);
        Console.Write((v-b-1)/(a-b)+1);
    }
}