2869 달팽이는 올라가고 싶다

백준 알고리즘 #2869

문제의 요구 조건에 따라

while문을 이용하여 day를 계산하면 된다.

달팽이가 나무 막대를 모두 올라가기 전까지는 올라가고 내려가고가 "반복" 되니까

이 지점(정상보다 높은 높이)을 break point로 설정하여 while문을 돌리면 해결된다.

def getDay(a, b, v):
    day = 0;
    # 현재 높이
    height = 0; 

    while True:
        day += 1;
        height += a;
        if height >= v:
            return day;
        height -= b;
    return;

def solution():

    # a : 낮에 올라가는 높이
    # b : 밤에 미끄러지는 높이
    # v : 나무의 높이
    a, b, v = map(int, input().split())

    day = getDay(a,b,v);
    print(day);

solution();

문제에서 제공되는 예제 입력을 수행했을 때 정확한 출력값이 나온 것을 확인할 수 있었다.

아주 간단한 문제이므로 이제 제출하면 끝!

아니 그런데 이게 무슨일인가

"시간 초과" 라고?

이게 얼마나 오래걸리는 연산이길래 시간 초과가 발생하는 건가

AI가 발전하고 RTX5090도 출시된 최첨단 시대에 이정도 계산도 수행하지 못하는 것이 말이 되는가?

그렇지 않다.

이 문제를 굳이 알고리즘 공부를 위해 선택한 이유가 있다.

왜냐하면 이 문제를 단순히 해결하는게 중요한게 아니라

최적의 방법으로 해결하는 것이 필요한 것이다.

바로 코딩에 "수학이 필요한 순간" 이다.

(* 책에서 소개된 알고리즘은 아닙니다.)

문제로 다시 돌아가서 이를 어떻게 해결할 수 있을지 고민을 해보자.

📌 문제의 핵심

달팽이는 낮 동안 A 만큼 올라간다.

밤 동안 B 만큼 미끄러진다.

마지막 날에는 밤에 내려가지 않고 정상에 도착하면 멈춘다.

목표 높이 V에 도달하는 최소 일수를 계산하는 것

낮에 A만큼 올라가고

밤에 B만큼 내려가기 때문에

하루동안에 올라갈 수 있는 높이는 (A - B)가 된다.

마지막 날(나무 막대를 통과한 시점)에는 내려가지 않기 때문에 A - δ 만큼 이동하게 된다.

( δ = A를 넘지 않으면서 V를 초과하지 않도록 보정하는 임의의 양수 → S - V )

S = (A - B) * (day -1) + A

V = (A - B) * (day -1) + ( A - δ )

| 🚀c.f] V는 항등식으로, 나눗셈 정리 꼴이다.

* 정식 B(x)를 정식 A(x)로 나누었을 때
B(x)=A(x)*Q(x)+R(x), (0 ≤ deg R(x) < deg A(x))를 만족시키는
정식 Q(x),R(x)가 유일하게 존재한다.
이때, Q(x)를 몫, R(x)를 나머지라고 한다.

V = (A−B) * Q(DAY−1) + R | R은 ( A - δ ) | | --- |

이렇게 표현할 수 있다.

S ≥ V 를 만족하는 최소 day를 구하면 된다.

이를 다시 표현하면

(A - B) * (day -1) + A ≥ V 이 된다.

이를 day에 대하여 정리하면

day ≥ [ (V - A) / (A - B) ] + 1

이때 day는 정수이므로 소수점 올림을 해야한다. day의 정의역은 int이기 때문이다.

예를들어 3.47 일이 필요하다고 하면

3일로는 부족하기 때문에 다음날까지 기다려야 해서 4일이 필요하다고 표현해야 한다는 뜻이다.

def getDay_v2(a, b, v):
    # 수학이 필요한 순간
    import math

    return math.ceil((v - a) / (a - b)) + 1

좀전의 수학적 추론과정을 통해서 요구사항을 충족하는 식을 세웠다.

무식한 방식의 getDay를 개선해서 getDay_v2를 만들었다.

🔥추가 고민

또한,

V = (A - B) * (day -1) + ( A - δ )

여기에서 δ를 구하고 싶다면

위 식을 δ에 대하여 정리하면 다시 구할 수 있다.

δ = (A - B) * (day -1) + (A - V)

getDay_v2로 day까지 구했으니 A,B,V,day를 알 수 있으므로 바로 계산할 수 있다.

🤔 굳이 구하는 이유는?

예를들어 어떤 기관의 예산 배정 시스템이 다음과 같이 되어있다고 하자.

예산은 언제나 한정되어 있으므로, 한 곳으로 과잉집중되는 것을 막기위하여

일종의 페이징(pagination) 개념을 적용하여, 우선순위에 따라 순차적으로 분배하도록 설계된 것이다.

그래서 지원 사업을 수행할 때 100만 원 단위로 지원(transaction)한다고 가정해보자.

즉, 한 번에 송금할 수 있는 최대 금액이 100만 원이라면,

필요한 예산을 여러 번 나누어 지원해야 하는 시스템이 필요할 것이다.

이를 시스템화 해서 관리하고 예산 배정 모듈을 작성한다고 하자

필요 예산이 530만원인 경우 5번으로는 부족하고 6번의 지원사업이 필요하다.

그래서 총 600만원을 지원받게 되는데

지원 받는 쪽에서는 70만원 이득이지만 예산 배정하는 쪽에서는 70만원의 추가지출인 셈이다.

따라서 이러한 시스템 허점을 방지하기 위하여

지원을 수행할 때, 지원금액이 필요 예산을 상회하는 경우,

잔여액만 송금해야 한다는 조건을 추가해야 할 것이다.

잔여액 = (1회당 지원 금액 - δ) 으로 산출된다.

이 잔여액을 구하기 위해서 δ가 필요한 것이다.

🕵️혹은 이 δ를 Salami Slicing처럼 활용할 수도 있다.

예를들어 시스템 레벨에서는 송금할 때 block단위로 전송된다고 하자.

이 경우, δ가 발생하더라도 요청한 기관으로 반드시 송금할 필요는 없다.

왜냐하면 해당 기관이 요청한 예산 금액만 충족하면 시스템적으로 문제가 발생하지 않기 때문이다.

또한, 예산 배정을 담당하는 기관 입장에서도,

필요한 블록 수만큼의 트랜잭션(transaction)이 정상적으로 발생했기 때문에

이상 징후를 쉽게 감지하지 못할 수도 있다.

그래서 이 구조를 잘 활용하면 δ가 발생할 때,

해당 금액을 별도의 계좌(예를 들면 모듈 개발자)에게 입금되도록 구현할 수도 있다.

😎 이런 시스템의 예산 배정 모듈 개발할 일이 있다면 저를 불러주세요!