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

문제 바로가기

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

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

---

 

관련 알고리즘

- 수학

---

정답 및 해설

달팽이가 매일 이동할 수 있는 높이를 입력받아 높이 V를 올라가는데 걸리는 일수를 구하는 문제이다.

매일 높이 상승분을 구하여 간단하게 해결할 수 있는 문제이다.

이때 예제 입력 3과 같이 올라가는 높이와 미끄러지는 높이의 차이가 크지 않은 경우,

간단하게 나눗셈만으로 정답을 구할 수 없다.

마지막날 나무 막대의 정상에 올라가고나면 더 이상 미끄러지지 않기때문에,

마지막날의 상승분을 미리 이동시켜놓고 나머지 높이를 올라가는데 걸리는 시간을 구하는 방법으로

정답을 구할 수 있다.

 

ex) V=10, A=4, B=1 인 경우, 1일차 : +4 -1=+3 / 2일차 : +4-1=+3 / 3일차 : +4(정상 도착)

위를 수식으로 표현하면

정답에 관한 식으로 정리하면 

⌈X⌉ 기호는 올림 기호로, X의 소수점을 반드시 정수로 올림하여 나타냅니다.

---

C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int A,B,V,ans;
    cin>>A>>B>>V;
    V-=A;
    ans=V/(A-B)+1;
    if(V%(A-B)!=0) ans++;
    cout<<ans;
}

 

Line	해설
4~5	풀이에 사용할 변수를 정의하고 cin함수로 A,B,V를 입력받는다.
6~7	V-=A 문을 통해 정상에 도착하는 마지막날 상승분을 미리 계산해 놓는다. ans=V/(A-B)+1 문에서 A-B는 매일 상승과 미끄러짐을 반복하여 최종 상승한 높이이다. V/(A-B)를 통해 매일 A-B미터 만큼 올라가서 V만큼 이동하는데 걸리는 시간(일수)를 구한다. 그 후, +1을 통해 미리 계산해 두었던 마지막날 1일을 더해준다.
8~9	V%(A-B)!=0 즉, V가 A-B로 나누어 떨어지지 않는다면 높이 V를 이동하는데 하루를 더 사용하여야 하므로 ans++ 문으로 정답에 1을 더해준다. (위 수식의 '올림' 과정에 해당한다)1) Line 9에서 ans를 출력하여 정답을 구한다.

1) cmath 라이브러리에서 제공하는 ceil 함수를 사용해도 좋지만 A,B,V의 자료형이 int 이므로 나머지를 계산하여 간접적으로 ceil 함수를 구현하였다.