[Baekjoon Online Judge] 백준 2869번 달팽이는 올라가고 싶다(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2869번 달팽이는 올라가고 싶다

(C++, Python)

(글쓴날 : 2020.04.19)

 

---

* Baekjoon Online Judge, 백준 2869번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

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

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2869

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

---

2) 풀이 과정

* 시간 복잡도 : O(1), O(log n)

 

낮 동안 A미터만큼 올라가고 밤 동안 B미터만큼 떨어지는 달팽이가 V미터인 나무 막대를 올라갈 때, 나무 막대를 모두 오르려면 며칠이 걸리는지 구하는 문제입니다.

단, 나무 막대기의 정상에 도달할 시 다시 떨어지지 않습니다.

 

저의 경우, C++로는 이분 탐색, Python으로는 수학을 적용하여 문제를 풀었습니다.

이 문제는 시간제한이 0.15초이므로, 아래의 Python 코드처럼 시간 복잡도가 O(1)인 상수 시간이 걸리는 공식을 구해 수학으로 해결하는 것이 맞지만, C++ 코드처럼 시간 복잡도가 O(log n)인 이분 탐색을 적용하여도 충분히 해결할 수 있습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
 
using namespace std;
 
bool isPossible(int rise, int oneDayRise, int destination, int day)
{
    int remainingDistanceOnTheLastDay = destination - oneDayRise * day;
 
    if (rise >= remainingDistanceOnTheLastDay)
        return true;
    return false;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int A = 0, B = 0, V = 0;
    cin >> A >> B >> V;
 
    if (A == V)
    {
        cout << 1;
        return 0;
    }
 
    int oneDayRise = A - B;
    int left = 1;
    int right = V;
    int mid = 0;
    int result = 0;
 
    while (left <= right)
    {
        mid = (left + right) / 2;
 
        if (isPossible(A, oneDayRise, V, mid))
        {
            right = mid - 1;
            result = mid;
        }
        else
            left = mid + 1;
    }
 
    cout << result + 1;
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
A, B, V = map(int, input().split())
 
print((V - A) // (A - B) + 1 if (V - A) % (A - B) == 0 else (V - A) // (A - B) + 2)

---