[백준] 달팽이는 올라가고 싶다 (C++)

 

문제 URL:

www.acmicpc.net/problem/2869

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

 

다음 문제는 달팽이는 낮에 A미터 올라가고, 밤에는 B미터 미끄러지는 달팽이가 

높이가 V미터인 나무 막대를 모두 오르려면 며칠이 걸리는지 구하는 프로그램을 작성하는 문제로,

달팽이가 정상에 도달하면 미끄러지지 않는다는 조건이 있다.

 

이 문제를 처음에 풀 때는 반복문을 사용하여 풀었는데 시간초과가 떴었는데, 알고보니 시간 제한이 0.15초인 문제였다.

정답률이 왜 낮았는지 그제야 이해가 됐다..

반복문을 사용한 코드

#include<iostream>
using namespace std;

int main()
{
    int a, b, v, num=0, count=0;
    cin >> a >> b >> v;
    
    while(true)
    {
        num += a;
        count++;
        if(num>=v)
            break;
        num -= b;
    }
    
    cout << count;
}

 

시간 제한을 보고 cin.tie(NULL)과 같은 실행 속도를 최적화 할 수 있는 코드도 삽입해보았지만 마찬가지로 시간초과가 떴다.

 

위와 같은 과정을 겪고 난 뒤 반복문을 사용하면 안된다는걸 깨닫고,

따라서 마침내 여러가지 경우에 대한 예시들로 규칙을 알아내어 코드를 작성하였는데 그 코드는 아래와 같다.

 

사실 규칙을 알아내어 푼 문제이기 때문에 이 규칙이 어떻게 나오게 된지 아직 정확하게 이해하지 못해서

지금은 설명을 하지못하겠다. 이 내용은 후에 다시 업데이트 할 예정이다.

---

#include<iostream>
using namespace std;

int main()
{
    int a, b, v, count;
    cin >> a >> b >> v;
    
    if(a==v)
        count=1;
    else if((v-a)%(a-b)==0)
        count=(v-a)/(a-b)+1;
    else
        count=(v-a)/(a-b)+2;
    
    cout << count;
}