백준알고리즘 #2869 달팽이는 올라가고 싶다 Java

백준알고리즘 #2869 달팽이는 올라가고 싶다 문제

V높이의 나무를 하루에 A만큼 올라가고 B만큼 미끄러지면서 얼마만에 꼭대기에 도달하는지 찾는 문제.

보기엔 얼핏 간단해 보이나 시간 제한(0.15초)가 걸린다.

 

시간 초과 코드

간단히 작성해 보았다.

a b v 는 주어진 보기와 같고

ht 는 달팽이의 현재 위치, 그리고 count는 날짜를 세는 용도이다.

날이 밝았을 때 a만큼 올라간 후 현재위치(ht)를 목표위치(v)와 비교하여 도달하면 반복문을 빠져나오고, 도달하지 못한다면 밤이되어 b만큼 미끄러지는 식으로 작성하였으나 결과는 역시 시간 초과.

 

정답 코드

따라서 변수를 더 추가한 후 간단히 구할 방법을 생각해보았다.

달팽이가 하루에 올라가는 높이를 구한 후 전체 높이에서 나눈다면 간단히 몇일이 걸리는지 알 수 있다.

다만 단순히 v / (a-b) 를 하게 된다면 100 99 100 인 경우에 100이라는 말도안되는 값이 나올 수도 있으니 정확한 값을 구하기 위해서 우선 ht 변수에 전체높이(v)에서 한번 올라가는 높이인 a를 뺀다(마지막날 도달하게 되면 더이상 미끄러지지 않으므로) 그리고 하루에 달팽이가 올라가는 높이는 a-b 이므로 day변수에 저장한다.

이때 ht (v-a)가 하루에 올라갈 수 있는 높이(day)보다 작다면 경우의 수가 2가지로 나뉘는데 

1. v 가 a보다 작거나 같은경우

 - 첫째날에 바로 목표지점에 도달할 수 있으므로 어떤 경우라도 1이된다.

2. v 가 a보다 큰 경우 (ex 10 1 11의 경우)

 - a보다 크다는 말은 첫날에는 도달할 수 없지만 둘째날에는 도달할 수 있으므로 2가 된다.

 

반대로 ht가 day보다 같거나 큰 경우에서도 마찬가지로 경우의 수가 2개 발생하는데

1. ht 를 day로 나눈 나머지가 0인 경우 (ex 10 2 18)

 - 나머지가 남지 않는다면 마지막날 이동 거리가 정확하게 목표지점에 도달하게 되는 경우이다.

 count = ht / day + 1 (처음에 v에서 a를 뺐으므로)

2. ht를 day로 나눈 나머지가 0이 아닌 경우 (ex 10 2 19)

 - 나머지가 남는다는 말은 이동할 거리가 남아있다는 말인데 '/' 연산을 할 경우 몫만 구하게 되므로 1의 경우와 같은 결과값이 나오게 된다. 실제로는 이 나머지 만큼 하루가 더 소비된다는 말이므로 1을 더 추가해준다.

 count = ht / day + 2