[알고리즘 문제 풀이][수학] 백준 2869번 - 달팽이는 올라가고 싶다

백준 2869번 달팽이는 올라가고 싶다 문제입니다.

(기초 수학 문제)

 

- 문제 설명: https://www.acmicpc.net/problem/2869

- 문제 풀이:

 

달팽이는 낮에는 막대를 오르지만, 밤에는 잠을 자는 동안 아래로 미끄러집니다. 그래서 총 거리를 오르기 위해서 총 며칠이 소요되는지를 구하는 문제입니다. 입력은 오르는 높이 (A), 미끄러지는 높이 (B), 총 거리 (V) 가 주어집니다. 문제의 조건은 (1 ≤ B < A ≤ V ≤ 1,000,000,000) 이기 때문에 미끄러지는 높이가 오르는 높이보다 더 길다거나, 총 거리보다 더 많이 오를 수 있지는 않습니다.

 

다만, 문제 풀이에 주의해야할 점은 마지막 날의 낮에 정상에 오르게 되면 이미 도착했기 때문에 미끄러지지 않는다는 것입니다.

 

입력

2 1 5

출력

4

전체 거리가 5인 경우, 첫날 2만큼 오른 후 밤에 1 미끄러져서 총 1 높이에 있게 됩니다.

다음날 2 만큼 오른 후 밤에 1 미끄러져서 총 2 높이에 있게 됩니다.

그 다음날도 2 만큼 오른 후 밤에 1 미끄러져서 총 3 높이에 있게 됩니다.

마지막 날에 2만큼 오르면 정상에 도달 (5) 하기 때문에 이 날까지 총 4일이 걸리게 됩니다.

 

- 코드: 

A, B, V = map(int, input().split())

step = A - B
dist = V - A
ans = 1 + (dist // step) + int(not(not(dist % step)))

print(ans)

마지막 날에는 미끄러지지 않기 때문에 올라간 것만 고려해서 V - A 로 거리를 수정하고 그 날 올라간 것을 고려하여 1을 미리 더해주었습니다.

그리고 마지막 날 전에는 하루에 (A - B) 만큼 올라갈 수 있으므로 1 + (V - A) / (A - B) 가 됩니다.

그런데, (V - A) 가 (A - B) 로 딱 나누어 떨어지지 않을 수 있기 때문에 나머지가 있는 경우 +1 일이 더해질 수 있도록 % 가 있는 경우 뒷 부분에 따로 처리를 해주었습니다. (dist % step 부분)

 

※ (V - B - 1) / (A - B) + 1 설명: https://www.acmicpc.net/board/view/22313
 마지막 날에는 미끄러지지 않기 때문에 V - A 대신 V - B 접근법도 가능하다고 합니다.

※ 나누어 떨어지는 부분을 제 코드처럼 따로 고려하지 않고 바로 위와 같이 간단한 식으로 한 번에 처리 가능한 이유: https://www.acmicpc.net/board/view/53443 혹은 https://www.acmicpc.net/board/view/44742

※ 현재 시간 제한으로 이분 탐색 코드도 가능한지는 확인이 필요합니다.

 

- 실수 포인트 & 반례:

1. 시간 초과

- for나 while 문으로 일일히 돌리는 경우 무조건 시간초과가 나게 됩니다. 일반화된 식으로 변경이 필요합니다.

- 운좋게 이전에 시간초과가 나지 않았던 코드들도 지금은 시간초과가 날 수 있습니다.

https://www.acmicpc.net/board/view/19765

- Java 에서 시간초과가 나는 경우 (1) 입출력을 먼저 확인해볼 수 있습니다. https://www.acmicpc.net/board/view/61920

(2) Java 11은 구동 시간에 0.3 초가 이미 걸리기 때문에 시간 제한 안에 들어오지 못합니다. Java 8 로 돌리는 것을 추천합니다. https://www.acmicpc.net/board/view/35534

- C# 도 Java (2) 와 같은 이유로 시간 제한에 걸릴 수 있습니다. https://www.acmicpc.net/board/view/40908

 

2. 자료형 관련 질문들

- 정수형을 나눠서 실수형 변수에 넣으려고 한 시도: https://www.acmicpc.net/board/view/55759

- double 이 아닌 float으로 해서 틀린 경우: https://www.acmicpc.net/board/view/67874 혹은 https://www.acmicpc.net/board/view/60592

(숫자 범위가 꼭 double일 필요는 없고, int 로 처리해도 됩니다)

 

3. 반례 모음

(1) 첫날에 다 올라가는 예시들

https://www.acmicpc.net/board/view/46667

5 0 5
1

https://www.acmicpc.net/board/view/56897

3 1 3
1

 

(2) 전체 높이가 낮에 올라가는 높이의 배수인 경우

https://www.acmicpc.net/board/view/67527

50 1 100
3

https://www.acmicpc.net/board/view/67198

3 1 6
3

https://www.acmicpc.net/board/view/53600

3 2 6
4

 

(3) 입력의 크기가 큰 경우

https://www.acmicpc.net/board/view/53284

2 1 1000000000
999999999

 

(4) 그 외

https://www.acmicpc.net/board/view/57117

4 2 7
3

https://www.acmicpc.net/board/view/16073

100 99 101
2

https://www.acmicpc.net/board/view/40766

249 125 500
4