문제출처 : 백준 2869번 - 달팽이는 올라가고 싶다

이 문제를 푸는 것은 어렵지 않다.
그렇지만 이를 함수를 쓰지 않고(예: math.ceil() 없이) 나타낼 수 있을까?

이에 대한 실마리를 찾기 위해 다음과 같은 상황을 생각해보자.

1. 가우스 함수로 올림 함수 표현하기

우리는 올림 함수를 가우스 함수 $[ ~~ ]$를 이용해 표현하는 방법을 두 가지로 나눌 수 있다.

정수일 때 적용할 수 있는 변형

$$
\lceil x \rceil = [ x - 1 ] + 1, \quad \text{(단, $x$가 정수일 때)}
$$

이 식은 $x$가 정수일 때만 성립한다.
예를 들어, $x = 3$이면 $\lceil 3 \rceil = [3 - 1] + 1 = [2] + 1 = 3$ (정확)
하지만 $x = 3.4$이면 $\lceil 3.4 \rceil = 4$인데, $\left[ 3.4 - 1 \right] + 1 = [2.4] + 1 = 2 + 1 = 3$ (틀림)
따라서 이 방식은 정수에 대해서만 유효하며, 소수에는 적용 불가하다.

분수일 때 적용할 수 있는 변형

$$
\lceil \frac{p}{q} \rceil = \Big[ \frac{p - 1}{q} \Big] + 1, \quad \text{(단, $p, q$는 양의 정수)}
$$

이 방식은 $p, q$가 양의 정수일 때 항상 성립한다.
예를 들어,
- $p = 10, q = 3$일 때:
  $$
  \lceil \frac{10}{3} \rceil = 4
  $$
  $$
  \Big[ \frac{10-1}{3} \Big] + 1 = \Big[ \frac{9}{3} \Big] + 1 = [3] + 1 = 4
  $$ (정확)
- $p = 7, q = 2$일 때:
  $$
  \lceil \frac{7}{2} \rceil = 4
  $$
  $$
  \Big[ \frac{7-1}{2} \Big] + 1 = \Big[ \frac{6}{2} \Big] + 1 = [3] + 1 = 4
  $$ (정확)
이 방식은 항상 성립하며, 특히 "분수" 형태의 값에 적용할 때 유용하다.

특수하게 정수를 논하는 문제에서만 첫번째 공식을 쓸 수 있고
사실은 두번째 공식은 정수이든 분수이든 성립한다 따라서, 두번째 공식을 쓰면 된다.
이 내용을 가지고 달팽이 문제를 풀며 된다.

2. 달팽이 문제 요약 및 식 유도

낮에 $A$미터 올라가고, 밤에 $B$미터 미끄러진다.
막대기의 높이가 $V$미터일 때, 달팽이가 며칠 만에 정상에 도달하는지 구해야 한다.
마지막 날에는 밤에 미끄러지지 않는다.

이를 올림 함수를 직접 쓰지 않고 정수 연산만으로 풀어내려면, 다음 공식을 떠올릴 수 있다.

$$
\left\lceil \frac{V - B}{A - B} \right\rceil = \Big[ \frac{(V - B) - 1}{A - B} \Big] + 1
$$

여기서 우리는 분수 형태의 올림 연산이 필요하므로, 앞서 소개한 두 번째 방식을 적용할 수 있다.

따라서 파이썬 코드는 이렇게 작성된다.

A, B, V = map(int, input().split())
cnt = (V - B - 1) // (A - B) + 1
print(cnt)

또한, 다른 유도 방식으로는 다음과 같이 시작한다.
낮에 $A$미터, 밤에 $B$미터 이동하고 마지막 날 밤에는 미끄러지지 않으므로,

$$
A + (n-1)(A-B) \ge V
$$

에서 출발하면

$$
n \ge \frac{V-A}{A-B} + 1,
$$

즉,

$$
n = \left\lceil \frac{V-A}{A-B} \right\rceil + 1.
$$

여기서
$$
\frac{V-A}{A-B} + 1 = \frac{V-A+(A-B)}{A-B} = \frac{V-B}{A-B}
$$
이므로,
$$
n = \left\lceil \frac{V-B}{A-B} \right\rceil
$$
와 같이 표현할 수 있고, 위의 정수 연산 식과 대수적으로 동치이다.

이제 우리는 분수의 올림을 정수 연산으로 변환하는 두 번째 공식을 활용하여 문제를 해결할 수 있다.

이와 같이, 정수 연산만으로 올림 기능을 구현하는 방법을 통해
math.ceil() 없이도 달팽이 문제를 정확하게 풀 수 있음을 보였다.
두 가지 방식

분자에서 바로 V - B를 사용하는 방식과
V - A를 사용하여 마지막에 1을 더하는 방식
은 대수적으로 동일하므로, 상황에 맞게 편리한 쪽을 선택하면 된다.

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