정답률이 낮길래 풀어봤다.

근데 낮은 이유가 있었다.

사실 문제 처음 봤을때는 입력이 매우 크길래 overflow 관련 함정이 있는 문제인 줄 알았는데 시간복잡도 관련 문제였다.

입력 값이 매우 크므로 일반적인 반복문을 활용한 풀이로는 시간안에 답을 구할 수 없다.

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long A,B,V; // 4 2 17
    cin >> A >> B >> V;
    long long goal = V-A; //전날 올라온 값이 처음으로 얘 이상이면 다음날에 무조건 도착함
    cout << (goal+A-B-1) / (A-B) + 1; 
    
    return 0;
}

이렇게 반복문 없이 풀어야만 시간제한 안에 들어올 수 있다.

전날 밤까지 올라온 높이 + 다음날 낮에 올라갈 높이 >= 목표 높이
즉 ,전날 밤까지 올라온 높이 >= 목표 높이 - 다음날 낮에 올라갈 높이 가 되면 된다.

를 만족하면 된다.

목표 높이, 다음날 낮에 올라갈 높이는 입력으로 받으므로 이미 아는 값이다.

전날 밤까지 올라온 높이만 구하면 된다.

전날 밤 까지 올라온 높이는 (A-B)*(일 수) 이다. 이 값이 V-A 보다 크거나 같으면 된다.

일 수 >= (V-A)/(A-B) 의 식이 나온다.

주의해야할 점이 일 수는 처음으로 >= 를 만족하는 값이고, 정수 이다.

그렇다면 어떻게 구해야할까? 올림? 내림?

(내림을 수행하면 전날 밤까지의 목표값에 도달하지 못하므로 올림을 수행해야한다)

처음으로 >= 를 만족하는 정수 이므로 (V-A)/(A-B) 에서 같거나 위로 가장 가까운 정수 가 일 수일 것이다.

(V-A)/(A-B) 를 어떻게 올림할까?

(V-A+A-B-1)/(A-B) 해주면 된다.

이 공식을 그림으로 나타내보면

이런 느낌이다.

d와 2d 사이에 값이 위치할때 +d-1을 통해 몫이 1이 나올것이 2가 나오게된다.

이렇게 나온 결과에 + 1(마지막 날) 을 해주면 답이 나온다.

1. 배운 점

(1) 입력의 범위에따른 시간 복잡도 조건에 주의하자

(2) 올림 공식