https://www.acmicpc.net/problem/2869
왜 이렇게 쉬운 문제가 나왔지? 하면서 바로 반복문 꽂아넣고 광탈당한 코드
#include <stdio.h>
int main(void){
int v=0, a=0, b=0, now=0, i;
scanf("%d %d %d",&a,&b,&v);
if(a>b && v<=1000000000){
for(i=1; now<=v; i++){
now+=a;
if(now>=v) {break;}
now-=b;
}
}
printf("%d",i);
return 0;
}시간제한 0.15초 내로 풀기 위해서는 반복문을 버려야 했다.
무슨 수학문제처럼 풀어야 하는 것 같더라.
A : 낮에 올라간 거리
B : 밤에 내려온 거리
V : 나무의 높이
따라서 A-B가 하루동안 올라간 거리라고 할 수 있다.
문제 조건에서 정상에 올라간 후에는 미끄러지지 않는다고 했으므로 만약에 낮에 나무의 정상에 오른다면 B만큼 내려오는 값을 감안하지 않아도 될 것이다.
단순한 수학계산 문제를 푼다고 생각해보자.
내가 어떤 거리까지 가는 시간을 구하고 싶다면 시간 = 전체 거리/오늘 이동 거리 로 구할 수 있을 것이다.
시간은 구해야 하는 값이니까 대충 i라고 두자. 오늘 이동 거리는 하루동안의 달팽이 위치의 변화량으로 대충 생각하면 A-B라고 할 수 있을 것이다. 그렇다면 거리는 어떻게 할까?
전체 거리를 V로 두려니까 달팽이의 낮과 밤의 위치가 유동적이라서 A-B의 거리로 V에 도달할때의 정확한 시간을 구하기가 어렵다. 그래서 이렇게 생각해 봤다.
달팽이가 낮에 A만큼 움직이고 밤에 다시 B만큼 내려온다. 그리고 다음날에 A만큼만 더 움직이면 달팽이는 문제 조건에 따라 더 내려오는 일 없이 V 정상에서 고정되어 있을 것이다. 따라서 달팽이가 V-A에 도달하는 지점은 하루만 더 있으면 정상에 도착할 지점이라는 것을 이용해 보자.
시간(i)=전체 거리(V-A)/하루 이동량(A-B)+1(다음날 낮에 A만큼 더 움직여야 정상에 도착하므로)
그러나 예외의 경우가 있었다.
입력값에 따라 시간이 2일이 걸리는 경우는 (V-A)/(A-B)의 나머지가 0으로 떨어지지 않았다. 따라서 이와 같은 경우는 int 형으로 소숫점을 버려버리고 +2를 더해주었다. 사실 이 부분에 대해서 제대로 된 서술을 못하겠다. 그냥 답이 2가 나오는 입력값들은 항상 나머지가 남았기 때문에 이런식으로 처리했지만 다른 사람 코드를 봐도 속 시원하게 설명해주는 걸 못봐서 일단 이렇게만 정리해야겠다. 제대로 나누어 떨어지지 않은 이유는 하루동안에 그 거리만큼 도달하지 못해서 하루를 더 추가했기 때문에 +2를 올렸다.
