백준_2869_달팽이는올라가고싶어

 

 

달팽이가 올라가는데 며칠이 걸리는지 구하는 문제입니다.

 

조건은 고려하지 않고 문제만 보면 쉬워보여서 바로 코드를 짜보았습니다.

 

#include <stdio.h>

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

    int i = 1;
    int height = 0;
    int count = 0;
    while (i)
    {
        height = height + A;
        count++;
        if (height >= V)
        {
            break;
        }

        height = height - B;
    }
    printf("%d\n", count);

    return 0;
}

 

 

단순히 다 올라갈 때까지 반복하고 다 올라가면 며칠 걸렸는지 출력하는 프로그램 입니다.

 

문제의 시간 제한을 보면, 0.25초로 굉장히 짧은 것을 볼 수 있습니다.

 

만약, 하루에 2미터 올라가고 1미터 떨어지는데, 나무 막대의 길이가 1,000,000,000 (십억) 미터라면, 

while 반복문을 999,999,999 번 돌아야 하기에 시간 초과가 발생합니다.

(아마 0.25초 제한이 아니라 더 널널하게 주어졌더라도 시간 초과 발생했으리라 예상합니다..)

 

 

그렇다면, 반복문을 사용하지 않고 수식을 이용해서 푸는 방법을 고안해보아야겠습니다..

 

수식을 이용하기 위해 문제를 잘 이해해야겠죠.

 

예시를 몇개 적어보겠습니다.

 

1. A=2 , B=1 , V=5 일 때.

하루에 2m 올라갔다가 1m 떨어지므로 하루에 1m 올라간다고 생각할 수 있습니다. (A-B)m.

걸리는 날짜를 미지수 x로 설정한다면 (2-1)*x = 5 라는 수식이 완성되죠.

 

하지만 이 수식은 틀렸습니다. 

 

막대의 꼭대기에 도달하면 떨어지지 않는다는 전제가 있으므로, 이 조건까지 추가해주어야 합니다.

 

달팽이가 막대기의 꼭대기에 도달했을 때, 한 번만 떨어지지 않으면 되므로, 막대기의 길이에서 떨어지는 길이만큼을 빼주면 조건을 충족할 수 있습니다. (V-B).

 

(2-1)*x = (5-1) -> x = 4;  //4일이 걸린다는 올바른 답이 나오죠.

 

 

2. A=5 , B=1 , V=6

위의 수식대로라면, (5-1)*x = (6-1) -> x = 1.25 라는 정수가 아닌 실수가 나오게 됩니다.

실수의 경우는 어떨까요??

 

이 문제에서는, 달팽이가 x일 안에 올라가지 못하면 무조건 x+1일 째에 올라가야 하는 성질이 있습니다.

따라서 소수점이 나온다면 올림을 해주면 됩니다.

 

규칙을 찾아 수식을 작성하였기 때문에, 간단하게 코드를 작성할 수 있습니다.

 

저는 미지수 x 대신 k 를 사용하였습니다.

 

전체 코드)

#include <stdio.h>

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

    double k = 0;
    k = ((double)V - B) / (A - B);    //수식을 코드로 작성한 것. k값을 구하기 위해 이항하였음.

    if (k - (int)k == 0)    //조건문을 통해서 k가 실수인지 정수인지 판단. 실수일 시 올림
    {
        printf("%d\n", (int)k);
    }
    else
    {
        printf("%d\n", (int)k + 1);
    }

    return 0;
}

 

반복문과 코드의 길이는 비슷하지만, 수식을 사용하여 시간이 훨씬 적게 걸리는 코드를 작성하였습니다.

 

수식만 이해한다면 코드도 매우 쉬운 것 같습니다.