[백준/C언어] 2869번 - 달팽이는 올라가고 싶다

백준 웹사이트 "2869번 - 달팽이는 올라가고 싶다" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

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

---

소스 코드

#include <stdio.h>

int main(void){
    int A, B, V;
    scanf("%d %d %d", &A, &B, &V);

    // n일: (A-B)*(n-1) + A >= V
    //      -> n >= (V-A)/(A-B) + 1
    // 따라서 (V-A)/(A-B)가 정수일 경우 그대로 정수가 아닐경우 1을 더해줌

    int n;
    if((V-A)%(A-B)==0){
        n = (V-A)/(A-B)+1;
    }
    else{
        n = (V-A)/(A-B)+2;
    }
    printf("%d\n", n);
}

---

문제 풀이

  A, B, V는 모두 10억 이하의 정수이므로, int형으로 선언해도 괜찮습니다 (int형의 최댓값은 (2^31)-1이죠). 하지만 이 문제의 시간 제한은 0.15초로 매우 짧기 때문에, 반복문을 사용하면 '시간 초과'가 뜰 것입니다. 따라서 수식으로, 반복없이 풀 수 있는 방법을 생각해봅시다.

  달팽이가 낮에는 A만큼 오르고, 밤에는 B만큼 미끄러지기 때문에 하루동안 A-B만큼 오릅니다. 문제 조건에 의해 A>B≥1이기에, 언제가는 반드시 정상에 오를 수 있습니다. 만약 달팽이가 n일을 오른다고 하면, 마지막 n번째 날에는 미끄러지는 것을 생각하지 않아도 됩니다. 따라서, (A-B)×(n-1)+A≥V의 수식을 만족하는 n의 최솟값을 구하면 충분합니다. 이때 마지막 날에는 1만큼 올라도, A만큼 올라도, 정상에 도달만 하면 되기 때문에 '≥'으로 이를 표현해줍니다. (A-B)×(n-1)+A≥V 라는 식은 n≥(V-A)/(A-B)+1 로 바꿀 수 있습니다.

  A, B, V 모두 int형이므로, (V-A)/(A-B)의 결과값 역시 int형입니다. 이 값이 본래 정수라면 이는 문제될 것이 없고, n의 최솟값은 (V-A)/(A-B)+1이 됩니다. 하지만 이 값이 본래 소수라면, 정수 부분만 저장이 되기 때문에 소수 부분만큼 모자르게 됩니다. 또한 '며칠'을 의미하는 n의 값은 항상 정수가 되어야 합니다. 따라서 이 경우, n의 최솟값은 (V-A)/(A-B)+2가 됩니다. 이를 코드로 표현한 것이 Line 11 ~ 17입니다.