[백준 알고리즘/ C++] BOJ.2869 : 달팽이는 올라가고 싶다

문제

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

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

 

---

풀이

자료구조

- int up : 낮 동안 올라가는 높이
- int down : 밤 동안 내려가는 높이
- int day : 올라가는 데 걸리는 시간
- int height : 막대의 높이

알고리즘
- 수학

- 구현

 

설명

입력 : 2 1 5

문제 풀이를 간단하게 하려면 저 과정을 그대로 코드로 쓰면 된다.

하지만 이 문제의 시간 제한이 0.15이기 때문에 이 문제는 식을 세워서 풀어야 한다.

 

달팽이는 하루에 2칸을 올라간다.

때문에 아침에 정상까지 남은 칸이 2칸보다 작거나 같을 경우 무조건 그 날에 목표까지 도달할 수 있다.

이를 바꿔서 말하면, 전날 밤 동안 달팽이가 내려간 위치가 (정상까지의 높이 - 하루에 올라갈 수 있는 높이)보다 작거나 같으면 된다는 뜻이다.

위의 예제에서는 3일차 밤에 달팽이가 3칸에 위치해 있기 때문에 ,위의 조건을 만족해서 4일차 낮에 올라간 것이다.

---

코드 

#include <iostream>
using namespace std;

int main() {
    int up = 0;  //낮 동안 올라가는 높이
    int down = 0;  //밤 동안 내려가는 높이
    int day = 1;  //올라가는 데 걸리는 시간
    int height = 0;  // 막대의 높이

    cin >> up >> down >> height;
    
    if(up >= height)  //낮 동안 올라가는 높이가 막대보다 길면
        cout << day << "\n";  //하루만에 올라갈 수 있음 day = 1
    
    else {  //하루 만에 올라갈 수 없으면
        
        //설명 참고
        height -= up;
        day = height / (up - down);
        if((up - down) * day < height) {
            day++;
        }

        cout << ++day << "\n";

    }
    return 0;
}

 

---

총평

팽이팽이 달팽이는 귀엽다.