[BOJ] 2896번: 달팽이는 올라가고 싶다 (Java)

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

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

---

 

 

<첫 시도: 반복문> 

반복문으로는 시간 초과가 나올 수밖에 없다.

일단 직관적으로 호기롭게 다음과 같은 반복문으로 문제를 풀었지만(심지어 처음에는 Scanner를 썼다 허허), 역시나 시간 초과!

'그래 그렇게 쉬울 리가 없지...' 싶었다.

Scanner보다 BufferedReader가 훨씬 수행 속도가 빠르다. 시간 제한이 빡빡하다면, 혹은 복잡한 알고리즘이 필요한 문제라면 BufferedReader를 쓰자.
(그런데 사실 최종적으로 푼 방법이라면 Scanner도 가능하다는...)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2869 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A, B, V;
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        int day = 1;
        int sum = 0;

        // 반복문을 쓰면 시간 초과
        while (true){
            sum += A;

            if (sum>=V)
                break;

            sum -= B;
            day++;
        }
        
        System.out.println(day);
    }
}

시간 초과!

시간 초과의 악마 등장...

위 풀이 방법은 사실 맞는 풀이긴 하지만, 반복문을 사용하기에 수행 시간이 너무 오래 걸린다.

그럼 도대체 어떻게 풀라는 걸까?

"수학"

 

조금 더 수학적으로 접근할 필요가 있다. 나는 수학 문제 풀듯이 문제의 조건을 따지고 식으로 정리를 해보았다.

 

<문제 해결>

위는 내가 조건을 정리하고, 차근차근 생각해보며 해결 방법을 도출해낸 자료이다.

일단 조건을 세 가지로 축약해봤다.

<조건>

1. 달팽이는 낮에 A미터 올라간다.
2. 달팽이는 밤에 B미터 미끄러진다(내려간다).
3. 달팽이는 V미터(정상)까지 이를 반복하며, 한번 정상으로 올라갔다면 미끄러지지 않는다.

<목표>

   총 이동 날짜 n(n은 자연수)을 구하자.

 

<풀이 1>

조건 1, 2만 고려할 시

만약 조건 1, 2만 고려 시 달팽이는 하루에 총 (A-B)미터만큼 이동한다.

즉 n일동안 V미터 정상까지(혹은 정상까지의 거리보다 더) 이를 반복할 것이므로 

n*(A-B) >= V
n >= V/(A-B)

n은 V/(A-B)이다. 하지만 조건 3이 중요하다.

 

조건 3까지 고려할 시

달팽이는 한번 정상으로 올라갔다면 굳이 미끄러져 내려 올 필요가 없다.

만약 정상에 도달하는 날, 그러니 일주의 마지막 날 낮에 A미터를 올라가 이미 정상에 도달했다면 밤에는 무조건 내려오지 않는다. (이는 풀이 2번의 모티브이기도 하다.) 즉 마지막 날에는 A미터를 올라가기만 한다.

 

따라서 마지막 날 전날인 n-1번째 날까지는 (A-B)미터씩 이동하고, 마지막 날에만 A미터를 이동한다.

총 이동거리는 A + (n-1)*(A-B)이 될 것이다.

n을 구하기 위해 식을 정리해보자.

A + (n-1)*(A-B) >= V(정상까지의 거리)
(n-1)*(A-B) >= V -A
n-1 >= (V-A)/(A-B)
n >= (V-A)/(A-B) + 1

 

n >= (V-A)/(A-B) + 1, 여기서 예를 들어보자.

만약 n >= 3 + 1, n >= 4라면 n은 4가 될 것이다.
      -> (V-A)/(A-B)이 나머지 없이 나누어 떨어짐.

하지만 n >= 3.5 + 1, n >= 4.5라면 n은 자연수(날짜 수니까)이므로 n은 5가 될 것이다.
      -> (V-A)/(A-B)이 나머지가 있음. 몫 3에 +1을 더하고 +1을 한 번 더 더한 것과 같은 결과

 

즉, 우리는 (V-A)/(A-B)가 나머지가 있는 경우와 나머지가 없는 경우로 나누어 코드를 짜야한다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2869 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A, B, V;
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        int day;
        day = (V-A)/(A-B);

        // 나머지가 있으면 1을 한 번 더 더해주어야 함 (아래 출력 연산까지 총 2를 더함)
        if ((V-A)%(A-B) != 0)
            day++;

        // 나머지가 없다면 1을 한 번만 더해주면 됨
        System.out.println(day+1);
    }
}

성공!

 

<풀이 2>

그런데 위와 다른 식으로도 코드를 짤 수 있다. 아까 앞서 언급했듯이 정상에 도달하는 마지막 날에는 낮에 A미터를 올라가고 반드시 내려오지 않는다. 즉, 매일 1번 올라가고 1번 내려오던 달팽이는 마지막 날에는 올라가기만 하지 내려오지 않는다.

따라서 총 이동 n일동안의 (A 이동 횟수)는 (B 이동 횟수) + 1이다.

 

총 이동 n일 동안 A는 n번, B는 n-1번 반복되었다.

A미터만큼 n번 올라가고(+), B미터만큼 n-1번 내려갔다(-).

V <= A*n - B*(n-1)
V <= (A-B)*n + B
V-B <= (A-B)*n
n >= (V-B)/(A-B)

 

n >= (V-B)/(A-B)에서 예를 들어보자.

만약 n >= 3이라면 n은 3이 될 것이다.
      -> (V-B)/(A-B)이 나머지 없이 나누어 떨어짐.

하지만 n >= 3.5라면 n은 자연수(날짜 수니까)이므로 n은 4가 될 것이다.
      -> (V-B)/(A-B)이 나머지가 있음. 몫 3에 +1을 더한 것과 같은 결과

 

역시 (V-B)/(A-B)가 나머지가 있는 경우와 나머지가 없는 경우로 나누어 코드를 짤 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A, B, V;
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        int day;
        day = (V-B)/(A-B);

        // 나머지가 있으면 1일을 더해주어야 함
        if ((V-B)%(A-B) != 0)
            day++;

        System.out.println(day);
    }
}

성공!

---

처음에 다른 사람들의 'V에서 A를 혹은 B를 뺀 것을 A-B로 나눈다...'라는 문제 풀이가 직관적으로 잘 이해되지 않아 코드를 읽고도 헤맸다. 하지만 직접 조건을 생각해보고 수학 문제 풀듯이 식을 써내려가니 왜 저러한 식이 조건에 나왔는지, 나머지가 있는 때와 없는 때를 구별해야하는 이유가 뭔지 이해가 아주 됐다!

오랜만에 백준 문제를 풀려니, 특히 내가 약한 수학 파트...라니 이해하는데 힘들긴 했지만 깨달은 점은 여튼 직접 해봐야한다는 거다! (쉬운 건 없다)

아.. 그런가보다하고 넘어가면 여간 찝찝한 게 아니니 차근차근 생각해보며 생각의 힘을 기르자고 다짐하게 되었다.

 

단맛나는 고구마를 향해서...