[BOJ] 백준 2869 달팽이는 올라가고 싶다

* 문제 난이도가 어려운 것은 아니지만, 시간복잡도 계산의 중요성을 새삼 느끼게 한 문제라 기록한다.

 

이미지를 클릭하면 문제 사이트로 이동합니다.

 

---

💣 문제 이해

 

문제에 나와있는 것처럼 달팽이는 낮에는 up만큼 올라가고 밤에는 down만큼 미끄러진다.

그러나, 정상에 올라간 후에는 미끄러지지 않는다.

즉, 낮에 up만큼 올라간 후에 나무높이 tree를 넘는다면 down만큼 차감하지 않아도 된다는 것이다.

 

그런데 간과하면 안 되는 것이 있다.

 

입력이 최대 10억까지 가능하다는 것,

그리고 시간제한이 0.15초라는 것...

 

💭 풀이 과정

 

처음에 작성한 소스이다. (시간 초과)

작성 언어: C++

 

#include <cstdio>
int main(){
    int up, down, plus = 0, tree, day = 0;
    scanf("%d %d %d", &up, &down, &tree);
    while(1){
        plus += up;
        ++day;
        if(plus >= tree) break;
        plus -= down;
    }
    printf("%d\n", day);
    return 0;
}

 

소스에 대한 설명을 하자면,

 

plus 변수에 매일마다 up을 더해준다. 물론 일 수를 나타내는 day도 1 증가.

매일 낮 up을 증가해준 이후, plus가 나무높이인 tree와 동일하거나 초과하면 루프를 탈출한다.

여전히 plus가 나무높이보다 작다면 밤에 미끄러지는 높이인 down 만큼 차감해준다.

 

루프를 탈출했다면, 달팽이가 나무를 올라갔다는 뜻이므로 일 수인 day를 출력한다....

 

예제는 완벽하게 실행됐지만 제출해보니 결과는 시간 초과...

up을 2, down을 1, tree를 최대 범위인 10억으로 해보니 실행시간이 2.894258이 나왔다...ㅋ

 

 

 

수정하여 작성한 소스이다.

작성 언어: C++

 

#include <cstdio>
int main(){
    int up, down, tree, num = 0;
    scanf("%d %d %d", &up, &down, &tree);
    while(1){
        num = tree - up;
        if(num % (up-down) == 0) break;
        tree++;
    }
    printf("%d\n", num/(up-down)+1);
    return 0;
}

 

소스 길이는 거의 동일하지만, 연산 횟수를 줄이기 위해 방식을 조금 바꿨다.

 

up down tree가 각각 7, 4, 14 인 경우를 계산해보았다.

1일 차	+7	-4	7 3
2일 차	+7	-4	10 6
3일 차	+7	-4	13 9
4일 차	+7		16

일차별로 총 달팽이가 오른 높이의 변화를 보면,

 

up과 down의 차이(3)만큼 증가하다가, 마지막은 항상 up이 합해질 때, tree 이상이 되면서 끝이 난다.

 

즉, 마지막 값이었던 16은 마지막으로 합해진 up을 차감하면 up-down인 3의 배수가 되어야 하는 것이다.

 

그래서 tree 값에서 1씩 증가해보면서 마지막 up을 제외했을 때, up-down으로 나누어 떨어지는 지를 체크하는 방법으로 짜보았다.

나누어 떨어진다면 그 지점이 마지막 지점인 것이고, 그 값에서 up을 빼고 up-down으로 나눈 (몫 + 1)이 답이 되는 것이다.

 

- 위의 경우를 예로 들자면, 16 - 7 = 9이고 9를 3으로 나눈 몫은 3(1,2,3일 차 총 3일).

   이 3일에 차감했던 4일 차인 1일을 더하면 4일. 답은 4일이 되는 것이다.

 

이 소스로 아까 돌려보았던 up을 2, down을 1, tree를 최대 범위인 10억으로 해보니 실행시간이 0.000076초...

 

 

🏆 배운 점

 

방식을 조금 바꾸었는데 실행 시간에 엄청난 차이를 가져왔다. 이 정도 간단한 소스인데 작은 변화로 효율을 낼 수 있다는 것은

더 길고 복잡한 체계의 소스, 더 크고 방대한 양의 데이터를 처리하면 그만큼 더 막대한 변화를 내는 것이겠지.

이래서 알고리즘을 공부하는구나 싶다..

 

같은 자원으로도 더 효율적인 성능을 낼 수 있는 개발자가 되기 위해 알고리즘 공부를 열씌미 해야겠당..!