티스토리 뷰
문제링크
https://www.acmicpc.net/problem/2869
2869번: 달팽이는 올라가고 싶다
문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽
www.acmicpc.net
풀이
풀이방법
순차적으로 달팽이가 움직이는 과정을 계산하여 풀 수는 있지만, 입력값의 범위가 크기 때문에 시간을 단축시키는 방법을 사용해야 합니다.
수학적인 방법으로 간단하게 풀 수 있지만 이진탐색을 이용하여 풀이를 진행했습니다.
이진탐색은 문제에서 다음과 같이 적용했습니다.
1. 나무막대의 첫부분을 start, 정상을 end라고 한다.
2. 중간지점을 달팽이가 올라가는 길이와 내려가는 길이의 차이로 나누어서 나온 값을 올려서 해당 지점에서 며칠이 걸렸는지 계산한다.
※ 왜 중간지점을 차이값으로 나누고 올리고 하는 과정을 진행했냐면, 달팽이의 위치가 낮과 밤의 반복에서 수학적인 규칙이 있기 때문입니다.
달팽이의 위치를 순차적으로 보면 다음과 같습니다.
[1일차 낮] A -> [1일차 밤] A - B -> [2일차 낮] 2A-B -> [2일차 밤] 2A-2B -> ...
그러면 n일차의 낮은 nA-(n-1)B, n일차의 밤은 nA-nB로 나타낼 수 있습니다.
이 식을 정리해보면 n(A-B) + B, n(A-B)로 정리되므로 나눈 값의 올림값이 해당 지점의 경과 날짜인 것을 확인 할 수 있습니다!
3. 해당 지점에서 낮에 움직인 거리로 종료조건을 검사한다.
3-1. 전체 막대의 길이와 전체 막대의 길이에 올라가는 길이와 내려가는 길이의 차이를 더한 값의 사이에 있다면 종료
3-2. 전체 막대의 길이와 올라가는 길이와 내려가는 길이의 차이를 더한 값 보다 크다면 end값에 mid값 할당
3-3. 전체 막대의 길이보다 작다면 start값에 mid값 할당
※ 특정 날의 낮에 움직인 거리가 전체 막대보다 작다면 달팽이가 아직 더 가야한다는 뜻이고, 그 반대이면 달팽이가 이미 그전에 도착했다는 뜻이다. 전체 막대와 전체 막대에 올라가는 거리와 내려가는 거리의 차이를 더한 값의 사이에 있다는 것은 그 날 달팽이가 도착했다는 뜻이다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] SWEA 2806 N-Queen (0) | 2019.11.02 |
|---|---|
| [알고리즘] SWEA 1868 파핑파핑 지뢰찾기 (0) | 2019.11.02 |
| [알고리즘] 백준 13460 (1) | 2019.10.13 |
| [알고리즘] 백준 2309 (0) | 2019.10.05 |