2869 - 달팽이는 올라가고 싶다

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

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

 

문제요약

• 달팽이가 낮에 A만큼 올라감.
• V 높이에 도달하면, 더이상 미끄러지지 않는다.
• 도달못한다면, 밤에 B만큼 미끄러진다.
• 1 ≤ B < A ≤ V ≤ 1,000,000,000
• 달팽이가 V 높이까지 올라가는데 걸리는 날을 출력

해당 문제는

단순히 while문을 돌면서 올라간 높이를 계속 누적합하고,
이때의 높이가 V인지를 확인한 후에, 아니라면 B 만큼 빼주고,
하루를 더해주고,...

이런 방법으로는 변수에 해당하는 값을 시간내에 출력하지 못한다.

즉, 문제를 몇번의 연산으로 날짜 계산으로 이어질 수 있게끔 코드를 짜야 했다.
이후 내가 생각한 공식은

(UP - DOWN) ==> 한번에 도달 못할 시, 하루에 올라가는 높이라면,
도달했을 때는
(UP - DOWN) m/day + UP m/day = 목표도달치(V) m 가 되는 것이다.

정리하면,
(V - UP) m = (UP - DOWN) m/day * day  의 식에서의 연관성을 찾는 것으로 시작했다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int up, down, height;
        up = sc.nextInt();
        down = sc.nextInt();
        height = sc.nextInt();
		
        // 도달하기 하루전 날짜
        int day = (height - up) / (up - down);
        
        // 도달하기 하루 전, 남은 거리
        int reg = height - day * (up - down);
		
        // 도달하기 하루전 남은거리가 up보다 작으면 하루만 더 올라가면 끝
        if(reg <= up){
            System.out.println(day + 1);
        }else{
            System.out.println(day + 2);
        }

    }
}

---

느낀점

나누는 과정에서 day가 최대치로 이미 계산되어지니까 하루나 이틀 더 올라가면 된다는 가정에서 시작한 코드이다.

기존에는 식으로 한번에 처리될 수 있는 것들도 거의 반복문을 돌리면서 처리했지만, 그 범위가 클 경우 시간이 많이 걸린다는 것을 알게되었다. 수학적 공식으로 접근했을 때, 쉽게 풀릴 수 있는 문제는 그 방법으로 접근하면 된다는 것을 알게 되었다.