오늘의 코드. 1일차 (백준/2869번 달팽이는 올라가고 싶다)

 

다시 처음부터 시작하는 코딩이니 만큼 쉬운문제를 고르고 고르던 중, 제목이 유난히 눈에 띄었다.
마치 지금 나의 상황을 그대로 나타내는 문장 같아서 이 문제를 고르게 되었다. 

 

 

Baekjoon / Problem No. 2869  (달팽이는 올라가고 싶다)

 

Problem

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다.

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

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

 

Input

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

Output

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

---

Solution 1

단순히 보면 쉬운 문제인것 처럼 보인다. 총 길이인 V에서 A(낮에 오른 길이) - B(밤에 오른 길이)를 나누어 몫을 생각하여 본다면 쉽게 나올것이다. 

다만 한가지 맹점(인가싶을 정도로 간단한)이 있다. 

낮 과 밤이 분리되어 있다는 점.

 

5미터가 되는 길이의 막대기(V)를 오르고, 달팽이는 낮에 2미터 오르고(A), 밤에 1미터 내려간다(B) 가정해보자.

위의 생각처럼 단순히 V / A - B 를 해보면 5가 나온다. 이렇게 풀면 반드시 틀릴것이다.

 

조금더 엄밀하게 생각해보자.

시간	1일차 낮	1일차 밤	2일차 낮	2일차 밤	3일차 낮	3일차 밤	4일차 낮	4일차 밤	5일차 낮
달팽이의 위치	2	1	3	2	4	3	5	4	6

 

표를 보면 확인할 수 있듯, 이미 4일차 낮에 5미터를 올랐다.

낮과 밤을 분리해서 각각  더하고 빼준다면 (올라감과 내려감을 개별적으로 계산) 풀 수 있다.

 

여기까지 생각해서 반복문을 통해 더하고 빼고를 반복해 보았다. 결과는 "시간초과"

Input 중에서 (1 ≤ B < A ≤ V ≤ 1,000,000,000) 조건이 굉장히 넓은 범위이기에 반복문을 썼다가는 시간초과가 발생한다.

 

과연 어떻게 해야할까?

---

Solution 2

거꾸로 생각해보자.

시간	1일차 낮	1일차 밤	2일차 낮	2일차 밤	3일차 낮	3일차 밤	4일차 낮	4일차 밤	5일차 낮
달팽이의 위치(m)	2	1	3	2	4	3	5	4	6

 

위의 표에서 '3일차 밤'을 보면 이미 3m를 이동하여 다음날 아침에 5m를 이동하여 도착할 것이 확정 되었다.

결국 V(총 거리) - A(낮에 올라가는 거리) 만큼 가면 다음날 도착하므로, V-A까지가는 시간 을 기준으로 

V-A / A-B  (도착 하루 전 거리 / 하루에 올라가는 거리)

 

를 하게되면 "도착 하루 전날까지 며칠이 걸리는지" 가 나오게 된다. (몫 = 도착 하루 전까지 걸린 시간)

 

나머지를 따져보자. 나머지가 있다면 내일 당장 A만큼 올라도 도착할 수가 없다.  

• 나머지가 없는 경우 = 다음 날이면 A만큼만 오르면 도착
• 나머지가 있는 경우 = 다음 날에 A만큼 올라도 조금 모자라...  →  + 1일

마지막으로, 위를 계산하고 나서 다음날 A만큼 올라가야 도착이므로 1일을 더해준다.

 

이를 코드로 정리하면 다음과 같다.

---

Code

#include <stdio.h>

int main()
{
    int v, a, b, day=0; // 걸린 '시간'을 나타내므로 0에서 시작한다.

    scanf("%d %d %d", &a, &b, &v);

    day += (v - a) / (a - b); 
    // (도착 하루 전 거리 / 하루에 올라가는 거리) 만큼 날짜에 더해준다.

    if ((v - a) % (a - b) != 0) 
    {
        day++;
        // 나머지가 있다면 내일 도착 할 수 없으므로 1을 더해준다.
    }

    day++; // 마지막으로, 다음날 A만큼 올라가야 하므로 1일을 더해준다.

    printf("%d", day);
    // 도착!
}

 

다음이 최종 코드의 사진 이다.

---

Review

사실 처음에 코딩을 할때는 무심코 반복문을 사용하여서 시간초과가 계속 발생했다. 

Solution 2의 해답을 찾기에는 꽤 걸린것 같다.

자원의 (메모리, 프로세서 등) 제한이 없다면 반복문을 쓰든 재귀문을 쓰든 상관이 없지만, 세상에 무한이란 없기에

더 머리를 싸매고 고민해야 했고 그런 과정이 코딩의 또 다른 재미가 아닐까?

 

코드를 짜는 시간보다 더 열심히 생각해야겠다는 생각이 들었고, 컴퓨터 앞에 앉아있던 시간보다

종이와 펜을 들고 고민한 시간이 많았던것 같아 의외였다. 새로움을 많이 느꼈다.

 

만만하게 생각하다가 문제에 뒤통수를 맞은것 같은데, 기분나쁘지 않고 오히려 속이 시원했달까.