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

문제

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

 

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #2 1번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: CHULMING, jm0707, tong39
• 문제의 오타를 찾은 사람: hellogaon
• 빠진 조건을 찾은 사람: jh05013

 

알고리즘 분류

• 수학

 

시간 제한

• node.js: 0.25 초
• C# 6.0 (Mono): 0.25 초
• C# 3.0 (Mono): 0.25 초
• VB.NET 2.0 (Mono): 0.25 초
• VB.NET 4.0 (Mono): 0.25 초

 

문제 출처

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

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

 

문제 해결 방법

• 반복문을 이용하여 문제를 풀 경우 시간 초과가 뜬다. 따라서 수식을 이용하여 문제를 해결해야 했다.
• 달팽이가 하루에 이동할 수 있는 거리(dist)는 낮에 이동한 거리(A) - 밤에 미끄러진 거리(B)이다.
• 이 문제의 핵심 포인트는 달팽이가 나무에 오르는 바로 전 날까지의 계산을 먼저 수행해주는 것이다.
  
  • 달팽이가 나무에 오르는 바로 전 날까지의 거리(V - A)를 달팽이가 하루에 이동할 수 있는 거리(dist)로 나눠준다.
    
    • 나머지 값이 0이 아닌 경우((V-A)%dist != 0)가 있을 수 있는데, 이 때는 하루 사이클을 한 번더 반복해야 하므로 1을 더해준다. (day++)
• 최종적으로 마지막 날에 달팽이가 이동하는 날을 포함한 day + 1 값을 출력해준다.

 

코드

#include <iostream>
using namespace std;

int A, B, V, day, dist;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> A >> B >> V;

    // 나무 높이 : V
    // 낮 : +A 미터
    // 밤 : -B 미터
    // 정상에서는 거리 변화 X
    dist = A - B;
    day = (V - A) / dist;

    if ((V - A) % dist != 0) {
        day++;
    }

    cout << day + 1 << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [기본 수학 1]
• 실버V