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

문제 링크

---

1. 아이디어

달팽이가 높이 $V$인 나무 막대를 올라가는데 하루에 $A$미터를 올라간 후 $B$미터를 내려오는 과정을 반복한다. 시간 제한으로 $V$미터가 될 때까지 이를 반복하는 방식으로는 해결할 수 없어서 수식으로 며칠이 걸리는지 찾아야 한다.

달팽이가 $V$미터인 나무 막대에 도착하려면 도착하기 전날에는 $V - A$미터 이상은 올라와야 한다. 여기서 $A$미터를 다음 날 올라가면 정상에 도착할 수 있다. 이때 $V - A$미터를 올라오는 데는 하루에 순수하게 올라갈 수 있는 높이가 $A - B$미터이므로 $\dfrac{V - A}{A - B}$일이 걸리게 된다. 이때 일 수는 자연수이어야 하므로 소수점에 해당하는 수가 있으면 올림 나눗셈으로 계산해야 한다. 예를 들면 5.7일로 계산되면 6일이 걸리는 것이다. 따라서 올림 나눗셈을 위해 분자에 분모에서 1을 뺀 값 $A - B - 1$을 더한 $\dfrac{V - A + (A - B - 1)}{A - B} = \dfrac{V - B - 1}{A - B}$일이 도착하기 하루 전날까지 걸리는 기간이고 여기서 마지막 날 한 번 더 오르면 정상에 도착할 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(1)$	$O(1)$

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        System.out.println((v - b - 1) / (a - b) + 1);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int a, b, v;
    cin >> a >> b >> v;
    cout << (v - b - 1) / (a - b) + 1;
}

---