[baekjoon 2869번] 수학 1 - 달팽이는 올라가고 싶다

문제

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

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

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

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

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

---

문제풀이

 

이 문제는 [1712번] 손익분기점과 굉장히 유사한 문제이다. 손익분기점에서도 그랬듯이 만약 반복문을 사용해서 처리하려한다면 시간초과가 발생할 것이다. 그렇다면 / 이나 %을 이용해서 문제를 풀어야 할 것이다.

 

처음에는 단순히 "V를 (A-B)로 나누면 되는 거 아닌가?" 라고 생각했다. 하지만 그렇게하면 오답이 발생한다. 왜냐하면 

A = 2, B = 1, V = 5일 때 달팽이는 3일차에는 3의 높이까지 올라갔을 것이다. 하지만 4일차에 5의 높이까지 올라갈 것이고 달팽이는 나무 막대 꼭대기에서는 미끄러지지 않기 때문에 4일차에 정상에 도달할 것이지만 V/(A-B)를 하면 5가 나오기 때문이다.

 

이런 문제를 방지하려면 나무막대 꼭대기에서 (A-B)만큼을 A보다 작거나 같을때까지 빼주고 1을 더하면 될 것이다. 하지만 뺄셈을 이용하면 시간초과가 발생한다. 그렇다면 어떻게 해야 할까?

 

사실 달팽이가 1번 올라갈 거리를 구하는 것은 중요하지 않다. 해당 거리가 있는지 없는지만 판별하면 해당 거리를 1번 올라갈 것이기 때문이다. 따라서 %을 이용해서 해당 거리가 있는지 없는지만 확인해줄 것이다.

 

---

소스코드

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        int cnt = (V-A)/(A-B);
 
        if((V-A)%(A-B)!=0) cnt++;
 
        bw.write(++cnt+"");
        bw.flush();
        bw.close();
    }
}

 

15번 줄 : 만약 달팽이가 하루동안 올라가는 거리가 낮에 올라가는 거리보다 작을 때 카운트가 안되는 경우 카운트가 되도록 해준다.

 

17번 줄 : cnt에 ++를 해주는 이유는 cnt가 나무 막대의 높이에서 달팽이가 낮 동안 올라갈 거리를 제외한 일 수이기 때문에 낮에 1번 더 올라갈 것을 생각해야하기 때문이다.

 

---

느낀점

 

알면 쉽지만 모르면 어려운 문제였다.