시간초과 feat.O(1)

BOJ 2869번 문제 시간제한 0.25초

 

for loop 1억번당 대략 1초라고 한다

입력 범위가 10억까지이니 아래와 같은 코드는 시간제한이 발생할 수 있다

    while(1)
    {
        day++;
        sum += a;
        if(sum >= v)
            break;
        sum -= b;
    }
    
    printf("%d", day);

 

 

for loop가 아닌 O(1)로 계산할 수 있는 방법을 찾아야 한다

방법은 아래와 같다

    day = (v-a) / (a-b);
    mod = (v-a) % (a-b);

    if(mod == 0)
        day++;
    else
        day = day + 2;

    printf("%d", day);