백준 2569번 - 달팽이는 올라가고 싶다 C++

📍 백준 2569번 - 달팽이는 올라가고 싶다 C++

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

 

 

🧩 문제요약

이 문제는 달팽이가 목표지점까지 몇일만에 올라갈 수 있을 지 구하는 문제다. 

문제가 매우 짧고 단순하기 때문에 for문으로 금방 해결 할 수 있어 보인다. 

 

하지만 for문으로 구현을 하면 시간초과에 걸리고 만다. 

그렇다면 어떻게 해결해야 할까? 

 

👍 이 문제에서 배울 점

여기서는 for문을 활용한 방법이 아닌 수학적인 수식을 발견해야 한다. 

달팽이는 낮에 a만큼 올라갔다가 밤에 b만큼 내려오게 된다. 

이 과정을 반복하면서 최소 몇일이 걸려야 목표 지점에 도달하게 될까?

 

이 문제에서 중요한 포인트는 "목표지점에 도달하면 더이상 내려오지 않다"는 것이다. 

 

달팽이가 하루에 실제로 올라가는 높이는 a-b이다. 

하지만 마지막날(목표지점에 도달한날)은 내려오지 않는다. 

그래서 마지막날은 -b를 고려하면 안된다. 

 

이 말을 정리하면, 

👉 하루에 a-b만큼 올라가는데 마지막 날은 a만큼만 올라가면 된다. 

 

이것을 수식으로 정리해보면, 

정상 v에 도달하기 위해, 마지막 날 올라갈 a를 미리 빼 주면 된다. 

•  v - a를 (a-b)만큼 나눠서 평소 처럼 오르는 날  수 계산  + 마지막 날 

이것을 코드로 구현하면 다음과 같다. 

#include <stdio.h>

int main(){
    long long a, b, v, day=0, snail_can_go; 
    scanf("%lld%lld%lld", &a, &b, &v);
    v -= a; 
    snail_can_go = a-b;
    if(v%snail_can_go == 0){
        day = v/snail_can_go;
    }
    else{
        day = v/snail_can_go;
        day++;
    }
    printf("%lld\n", day+1);
    return 0;
}

나머지가 있는 경우 하루 더 움직여야 하기때문에 다음과 같이 구현했다. 

 

 

 

하지만 백준 상위 코드를 살펴보면 다음과 같이 구현한것을 알 수 있다.

#include<cstdio>
int A,B,V;main(){scanf("%d%d%d",&A,&B,&V);printf("%d",(V-B-1)/(A-B)+1);}

 

 

✅  왜 v-a가 아닌 v-b일까? 

 

위의 접근은 마지막 날은 밤에 미끄러지지 않으니 그 전날까지는 하루에 (a-b)만큼 올라가고 마지막 날은 a만큼만 올라가면 끝이라는 정석적인 접근이다. 

 

아래의 코드에서 밤에 안 미끄러지고 도달하는 순간을 기준으로 계산한거다. 

👉 즉, 정상 이상을 넘어선 순간이 언제인지를 계산한 것이다. 

 

#include<cstdio>
int A,B,V;main(){scanf("%d%d%d",&A,&B,&V);printf("%d",(V-B-1)/(A-B)+1);}

v-b는 만약 낮에 올라간 뒤, 밤에 미끄러져도 다음날 v이상이 되는 최소한의 높이로  v-b 이상에 도달하면, 밤에 내려와도 다음날 v이상을 유지할 수 있다.

즉, 그 전날까지 올라가면, 다음 날 낮에 끝낼 수 있다는 의미이다. 

 

그래서 v-b를 사용했고 올림 계산을 위해 -1을 해준 것이다. 

 

 

나는 정말 어떻게 수식을 정리해야할지 몰라 여리저리 삽질을 했는데, 이렇게 간단명료하게 구현할 수 있는 것이 놀랍다. 

그리고 올림계산은 여기저기 많이 사용하는것 같으니 꼭 익혀두고 사용하도록 하자. 

 

cf) a를 b로 나눈 값을 올림(ceil):

(a+b-1)/b