[C++] 2869번: 달팽이는 올라가고 싶다

그냥 주어진대로 반복문을 활용해 풀면 시간초과가 발생하는 문제.

수식을 세워야 함.

 

(day - night)*x > height로 구하면 안된다. 

이 조건을 위배하기 때문.

낮중에 이미 정상에 올라갔는데 그날 밤에 내려가는 걸 계산했을 시, 높이 미달성인 경우를 고려하지 않은 수식이다.

 

즉, 위 수식은 '밤 기준'으로 세워진 수식이기 때문에, 높이를 갱신하게 되는 '낮 기준'의 수식을 세워야 한다.

 

day x일의 높이는 어떻게 구할까?

x일만큼 낮에 올라간 거리에서 (x-1)일만큼 밤에 내려간 거리를 빼면 된다.

x*day - (x-1)*night > height 를 달성하는 최소 정수값 x를 구하면 끝이다.

식을 잘 정리하면 x > (distance - night) / (day - night) 이다.

항상 이런 나누기 부등호 문제는 두가지를 고려해야한다.

 

1. 분모가 0일 경우 -> 예외조건 처리

2. 분모가 음수일 경우 -> 부등호 반대로 변경

 

그러나 이 문제에서 항상 낮 이동거리>밤 떨어지는 거리라고 값 범위 지정이 되어있기 때문에 1,2번의 문제 모두 발생하지 않는다.

 

    int day, night,distance, date;
    cin >> day >> night >> distance;
    date = (distance - night) / (day - night);    
    cout << date;

그러나 이렇게 내면 안된다. 반례로 5 1 6이 2가 아니라 1을 출력한다.

그 이유는... int값인 date에 분수가 들어갈 경우, 무조건 내림처리를 하기 때문이다.

5 1 6의 경우 x > 5/4(== 1.25) 의 수식으로, x = 1이 되어버리기 때문임.

double로 받아서 처리하는 경우가 있겠지만 좋은 처리법이 아니라고 생각하여 직접 검사문을 하나 넣었다.

    if((distance - night) % (day - night) != 0) {
        date++;
    }

나머지가 0이 아닐경우(분수일 경우) 내림처리가 되어버린 date에 직접 1을 더해준다.