[백준 - C++] 2869번: 달팽이는 올라가고 싶다

기본적인 방정식을 응용한 문제이다. 그러나 올라가고 떨어지는 것을 번갈아가면서 순차적으로 한다는 점을 주의깊게 봐야 한다. 조건 중에 "정상에 올라간 후에는 미끄러지지 않는다." 라는 부분을 잘 고려해야 이 문제를 맞을 수 있을 것이다. 그리고 추가적으로, 깐깐한 시간 제한 때문에 C++의 cout, cin을 사용할 시에는 시간초과가 날 수도 있으므로 비교적 더 빠른 printf와 scanf를 사용할 것을 권장한다. 답은 맞혀도 시간제한에 걸리면 말짱도루묵이다.

#include <iostream>

int main(void) {
    int A, B, V;
    scanf("%d %d %d", &A, &B, &V);
    if(A >= V)	//한 번에 올라가는 높이가 올라가야 할 높이보다 높을 때
        printf("1\n");	//1 출력
    else{
        int d;
        if((V-A) % (A-B) == 0)
            d = (V - A) / (A - B) + 1;
        else
            d = (V - A) / (A - B) + 2;
        printf("%d\n", c);
    }
    return 0;
}

올라가는 거리를 A, 내려가는 거리를 B, 올라가야 할 거리를 V라고 두고 입력을 받는다. 

만약 올라갈 수 있는 거리가 올라가야 할 거리보다 크거나 같은 경우에는 하루가 걸리는 것이므로 1을 출력하고 종료한다. 그렇지 않은 경우에는 새로운 변수 d를 선언하고, d에 조건문을 통해 다음과 같은 식을 대입한다.

 

"d = (V - A) / (A - B) + 1" or "d = (V - A) / (A - B) +2"

 

이 식이 도출되는 과정은 바로 이렇다. 

 

우선 우리가 염두에 둬야 하는 것은 정상에 한 번 도달하면 미끄러지지 않는다는 조건이므로, 하루에 A-B 씩 c일을 이동한다고 했을 때 최소 V-A 이상을 이동하면 그 다음날에 도착지에 도달한다는 것이다. 

그림으로 그려보면 이렇다는 것이다.

결국 식으로 나타내보면 (A-B) * c를 했을 때 최소한 그것이 V-A와 같거나 더 커야된다는 것이다.(그래야 다음날에 도착지에 도착하므로)

 

그 다음으로 고려해야 할 점은 c의 값이 이산변수라는 것이다. 왜냐, 문제에서 구하라고 하는 것은 걸린 일 수이므로 1.5일, 2.8일 이런 값은 나와서는 안되는 것이다. 1.5일이 걸렸으면 2일이 걸린 것이고, 2.8일이 걸렸으면 3일이 걸렸다고 생각해야 한다.

 

그렇기에 c는 정수여야 한다. 그러나 식의 형태를 보면 (V-A) / (A-B)가 항상 정수를 반환하지는 않음을 알 수 있다. 분명 1.5, 2.8과 같은 실수형이 도출될 수 있기 때문에 지금부터는 그것을 신경 쓰고 두가지 조건으로 나눠보고자 한다.

 

1) (V-A) / (A-B)가 딱 나눠질 때 

이해를 돕기 위해 그림을 그려보았다.

값이 딱 나눠떨어지므로 c가 1.5나 2.8이 되어서 정수형으로 형변환했을 때 1.5가 1이 되고, 2.8이 2가 되는 경우가 발생하지 않는다.(문제에서 원하는대로 값을 도출하려면 1.5->2, 2.8->3으로 변환되어야 한다.) 결국 최종적으로 이동한 일 수인 d는 c+1(다음날)을 해서 구할 수 있다. 

d = c + 1 = (V-A) / (A-B) + 1

 

2) (V-A) / (A-B)가 딱 나눠지지 않을 때

그럼 나눠떨어지지 않는다는 건 무슨 소릴까. 필자가 지겹도록 예시를 들고 있는 1.5가 1이 되고, 2.8이 2가 된다는 의미다.(문제에서 원하는대로 값을 도출하려면 1.5->2, 2.8->3으로 변환되어야 한다.) 즉, 원래 구해져야 하는 c값에서 1씩 작아진다는 것.

그림으로 설명하자면 이렇다.

우측 예시에서 볼 수 있듯이 원래 c는 3이다. 왜냐 A-B인 2를 3일동안 이동하면 6만큼 이동하는 것이고, 그 다음날에 4만큼을 추가로 이동한다면 10이 되어서 도착지에 도착하는 것이기 때문이다. 그렇지만 식의 나눗셈에서 정수형으로 변환하는 과정에서 소숫점 이하의 숫자가 무시당하게 되어 결국 원래 구해져야 하는 값보다 1이 더 작아지게 되는 것이다. 그렇기 때문에 원래 c의 값보다 하나 작아져 있는 (V-A) / (A-B)에다가 우선 1을 더해서 원래의 c값으로 원상복귀를 시켜주고, 최종적으로 그 다음날 도착지에 도착하므로 1을 한 번 더 더해줘야 한다. 그래서 d = c + 2가 된다.

d = c + 2 = (V-A) / (A-B) + 1 + 1 = (V-A) / (A-B) + 2

 

일견으로는 간단해보이지만 식을 세우려고 생각을 해보면 그렇게 쉽지만은 않았던 문제 같다. 문제를 풀면서도 자신을 이해시키고 납득시키는데 오랜시간이 걸렸다ㅠ. 혹시 이 블로그를 보고 있는 다른 분들도 이 문제가 잘 풀리지 않는다면 예시를 들어가면서 자신을 납득시키려고 해보면 좋겠다!

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

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

p.s. <cmath>라이브러리중에 ceil()함수를 이용한다면 d = c + 1 = (V-A) / (A-B) + 1의 형태로 정리할 수도 있을 것 같다!

#include <iostream>
#include <cmath>
int main(void) {
    int A, B, V;
    scanf("%d %d %d", &A, &B, &V);
    if(A >= V)
        printf("1\n");
    else{
        int d;
        double c = ((double)V - A) / (A - B);
            d = ceil(c) + 1;
        
        printf("%d\n", d);
    }
    return 0;
}