[BOJ/C++] 2869::달팽이는 올라가고 싶다

 

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 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

 

---

후기

이번에도 패턴을 찾는 것에 실패하고 다른 분들의 풀이를 보았다.

 

기본적으로 정상에 도착하는 높이를 구해야한다.

 

정상에 도착할 수 있는 높이 = (도착 전날) X (하루에 올라갈 수 있는 높이) + 올라가는 높이

 

이를 수식으로 전환하면 다음과 같다.

 

도착날 = n, 하루에 올라가는 높이 = u, 하루에 내려가는 높이 = d, 정상 높이 = h
$h = (n - 1) * (u - d) + u$

 

 

이를 이제 도착날만 남도록 수식을 변경한다.

 

u 제거하기
$h - u= (n - 1) * (u - d) + u - u$

(u - d) 제거하기
$\frac{(h - u)}{(u - d)} = \frac{(n - 1) * (u - d)}{(u - d)}$

1 제거하기
$\frac{ (h - u) }{(u - d)} + 1 = n - 1 + 1$

n 공식 완성
$n = \frac{ (h - u) }{(u - d)} + 1 $

 

이제 도착날을 구할 수 있는 공식이 생겼다. 코드에 넣어보면 된다.

 

int main(void) {
    int v, a, b;
    int days = 0;
    cin >> a >> b >> v;
    
    days = (v - a) / (a - b) + 1;
    
    return 0;
}

5 1 6
1

 

그런데 여기서 문제가 생겼다. 모든 변수가 int형이기에 나눗셈으로 발생하는 소수점이 전부 버림 연산처리가 된다.

 

저 공식은 도착하는 높이에 도달하는 시간을 구하기에 나머지가 남는다면 반드시 소수점의 결과가 나오게 된다.

 

그러므로 나눗셈 연산을 double형으로 형변환하고 문제가 요구하는 정답은 "도착 날짜 + 시간"이 아닌 "도착 날짜"이기에 올림연산을 해주어야 정확한 날짜를 출력한다.

 

#include <iostream>
#include <cmath>
using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int v, a, b;
    int days = 0;
    cin >> a >> b >> v;
    
    days = ceil((double)(v - a) / (a - b)) + 1;
    
    cout << days;
    
    return 0;
}

 

 

참고

달팽이는 올라가고 싶다 문제 풀이 해설 C, C++, 자바 [백준 2869번, COCI 2010/2011 기출문제]