[백준 알고리즘] 2869번 달팽이는 올라가고 싶다.

문제

---

시간 제한  :  0.15초               

메모리 제한 : 128MB        

 

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

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

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

입력

---

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

 

출력

---

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

풀이

---

문제 자체는 굉장히 쉽다. 프로그래밍 언어 책을 접하게 되면 늘 초반부에 등장하는 문제 중 하나인데 

대신, 해당 문제는 시간 초가 걸려있어 반복문을 사용해서는 안된다. 따라서 간단한 수학적 사고력이 요구되어 진다.

이 문제를 쉽게 풀기 위해서는 자신이 직접 그림을 그려본 후, 수식을 완성하고 코드를 작성하는 것이 좋다.

 

달팽이는 A-B만큼 몇날을 올라가고, A만큼 올라간 후 도달한다고 가정하자. 그러면 아랫부분의 길이는 V-A가 될 것이고 

윗 부분은 A가 될 것이다.

 

여기서 집중에서 봐야할 부분은 달팽이가 목표에 도달할 때 즉, A 부분이다.

 

1. 만약, 아랫 부분 즉, V-A 와 A-B를 나눴을 때 나머지가 없는 경우

2. 반대로 나머지가 있는 경우 (여기서 나머지는 무조건 A-B보다 작다.)

 

첫번째의 경우에는 V-A / (A-B) + 1이 정답이다. 왜냐하면 나머지가 없다는 것은  딱 A만큼 남았다는 의미이기 때문에 하루만 더 올라가면 달팽이는 미끄러질 필요 없이 목표에 도달하게 된다. 

 

하지만 두번째의 경우 A + 나머지 만큼 더 올라가야 하기 때문에 달팽이는 A를 올라간 후 한번 미끄러질 수 밖에 없다. 

따라서 첫번째와 다르게 하루를 더 추가적으로 올라가야 하기 때문에 +2를 해줘야 한다. 여기서 누군가는 의문을 가질 수도 있다. "1일이 아니라 그 이상을 더 올라갈수도 있지 않을까?"라고 말이다. 하지만 위에 언급한 것처럼 나머지 값은 A-B (A > A-B, B >= 0) 보다 무조건 작을 수 밖에 없기 때문에 1일을 초과할 수가 없다. 

코드

 

import java.util.*;
 
class Snail {
    int A;
    int B;
    
    Snail(int A, int B) {
        this.A = A;
        this.B = B;
    }
}
 
public class snailCheck {
    public static void main(String[] args) {
        int V,A,B = 0;
        Scanner scanner = new Scanner(System.in);
        A = scanner.nextInt();
        B = scanner.nextInt();
        V = scanner.nextInt();
        Snail snail = new Snail(A,B);
        System.out.println(snailDayCheck(V,snail.A,snail.B));
    }
    
    public static int snailDayCheck(int V,int A,int B) {
        int sum = 0;
        int day = 0;
        int other = 0;
        int V2 = 0;
        
        V2 = V - A;
        day = V2 / (A-B);
        other = V2 % (A-B);
        
        if(other == 0)
            return day + 1;
        
        return day + 2;
        
    }
}