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

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

문제

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

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

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

입력

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

출력

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

풀이

맨처음엔 단순히 반복문을 활용하여서 풀이할려고 했지만, 시간초과의 덫에 걸려버렸다.

시간제한 0.25초이기 때문에 높이가 높아져버리면, 수행시간이 오래걸려서, 반복문으로 풀라는 문제는 아니고, 수학적인 계산 식을 생각해서 문제를 풀이해야한다.

하루에 통틀어 올라갈 수 있는 높이는 A-B만큼 올라갈 수 있고, 정상에 올라가기만 하면,  더이상 내려올 필요는 없다.

따라서,  올라갈 높이를 (A-B)만큼을 나누어주어야 하는 것은 맞지만, 예외 케이스들을 생각해야한다.

n일만에 달팽이가 정상에 도달한다고 생각해보자, 그렇다면 달팽이가 올라간 높이는 n-1일동안 A-B만큼 올라갔을 것이고, 마지막 날에는 A만큼 올라가는 도중에 정상에 도달하게 된다. 이는 1만큼일수도 있고, A만큼일수도 있다.

수식으로 나타내면 (n-1)(A-B)+A>=V>=(n-1)(A-B)+1 에 해당하는 n 값을 찾는 것이 문제의 핵심이 되겠다.

좌변부터 n에 대한 식으로 정리해보면

n>=(V-A)/(A-B)+1 

우변의 경우

(V+A-B+1)/(A-B)>=n 가 된다.

n의 최소값과 최대값이 1차이 안쪽으로 나게 될 것이므로, 결국 n의 최소값만을 구하면 되겠다.

따라서, 좌변을 정리한 식만 넣어주면 되는데, 문제는 int 형을 사용하기 때문에, 예를들어 5.3 이런 값이 나눗셈 몫으로 나타난다면, int 형이기 때문에 5만 출력이 될 것이고 이는 실제로 6일이 걸리는 것인데, 5일로 답이 나오게 되어 오답이 된다.

따라서, 여기서 case가 나뉘어져야 한다. 만약 몫이 딱 정수값으로 나온다면 그 자체로 답이 되지만, 5.3 이런식으로 나오게 될 경우 나온 몫에서 +1을 해주어야 한다. 즉 % 를 활용하여 나머지를 체크하여 마무리 하면 되겠다. 

#include <iostream>
using namespace std;

int main()
{   

    int A, B, V;
    cin>>A>>B>>V;
    
    int day;
    
    if((V-A)%(A-B)==0){ //정수인지 체크
        day = (V-A)/(A-B)+1;
    }
    else{ //정수가 아니고 5.3 같은 소수라면 +1
        day = (V-A)/(A-B)+2;    
    }

    cout<<day;
        
    
}

맨처음에 반복문으로 했다가 실패하여 여러번 틀리고 나서 얻은 결과이다.

이제 코드를 작성할 때에 연산량을 고려하면서 생각을 해야한다.