https://www.acmicpc.net/problem/2869
2869번: 달팽이는 올라가고 싶다
첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
www.acmicpc.net
[문제]
[풀이]
● 세 정수 A, B V 입력받기
● 달팽이가 하루에 올라갈 수 있는 높이는 (A-B)이다.
● 정상에 올라간 후에는 미끄러지지 않는 경우를 생각해야 한다.
하루에 2M를 올라가고 1M가 떨어지며 꼭대기는 5M라고 가정을 해보자
1. 첫째날에는 오전에 2M를 올라가고 오후에 1M가 떨어져서 총 1M를 올라갔다
2. 둘째날에는 오전에 2M를 올라가서 총3M를 올라왔고 정상에 도달하지 못했으므로 오후에 1M가 떨어질 것이다
그러므로 둘째날에는 총 2M를 올라가게 된다.
3. 셋째날에는 오전에 2M를 올라가서 총 4M를 올라왔고 정상에 도달하지 못했으므로 오후에 1M가 떨어질 것이다
그러므로 셋째날에는 총 3M를 올라가게 된다
4. 넷째날에는 오전에 2M를 올라가서 총 5M를 올라왔고 정상에 도달했기 때문에 오후에 떨어지지 않을 것이다.
그러므로 넷째날에 달팽이는 정상에 도달했다.
● 위 과정에서 식을 생각해볼 수 있다.
셋째날 까지는 (A-B)*DAY 의 식으로 올랐고 넷째날에는 (A-B)*DAY + A 가 되어 높이가 되었다.
(A-B)*DAY+A>=높이(V) == (A-B)*DAY>=V-A == DAY>=(V-A)/(A-B)
위와 같은 식이 만들어지는 것이다.
즉 DAY의 최솟값을 구한뒤 +1을 해주면 정답이 나오는 것이다
여기서 +1을 해주는 이유는 뒤의 +A도 1일에 포함되기 때문이다.
위의 식에 예제를 대입해보도록 하자.
(2-1)*DAY+2>=5 -> (2-1)*DAY>=3 -> 1*DAY>=3
DAY의 최솟값은 3이므로 3+1=4
총 4일이 소요된다.
● 두번째 예시를 들어보자
1. A=5 B=1 V=6
2. 위 식에 대입해보자
(5-1)*DAY+5>=6 -> (5-1)*DAY>=1 ->4*DAY>=1 -> DAY>=0.25
DAY가 정수형이아니라 실수형이 나왔다.
첫번 째 예시같은 경우 (V-A)/(A-B)를 하면 딱 나누어 떨어져 나머지가 0이었다
V-A=3 이고 A-B=1이다 3/1을 해보면 몫이 정수형으로 나누어 떨어지고 3%1 는 0이다.
(V-A)%(A-B) 가 0인 경우이다.
즉 달팽이가 3일만큼 올라간 후 +2를 더햇더니 딱 정상의높이(5)가 되었다는 말이다.
따라서 3일 + 1일(+2도 1일이기 때문에)
총 DAY= (V-A)/(A-B)+1
두번 째 예시같은 경우
V-A=1 이고 A-B=4이다 1/4는 몫이 0.25로 나누어떨이지지 않고 1%4 는 1로 나머지가 있다.
(V-A)%(A-B) 가 0이 아닌 경우이다.
즉 달팽이가 몫만큼의 DAY(0일)를 올라가서 +A를 해도 나머지 1이 부족하다는 말이다.
나머지만큼의 높이만 부족하기 때문에 1일을 더 추가해주면 된다.
+A에서 1일을 추가하였고 그럼에도 불구하고 꼭대기에 도달하지 못햇으므로(나머지 만큼 부족) +1을 더 더해주면 총DAY를 구할 수 있다
총 DAY=(V-A)/(A-B)+2
댓글