18324 - Race

문제

* 오역 주의

Bessie 는 K (1 <= K <= 10^9) 미터의 경기를 달리고 있다.
그녀는 1초당 0 미터의 스피드로 달리기를 시작했다. 주어진 초에, 그녀는 초당 1미터씩 스피드를 올리거나,
계속 유지하거나, 초당 1미터씩 줄일 수 있다.

예를 들어, 처음 1초에, 그녀는 초당 1미터로 스피드를 올려서 1미터를 달릴 수 있고, 혹은
1초에 0미터로 스피드를 유지해서 0 미터를 달릴 수도 있다.

Bessie 의 스피드는 0 이하로 떨어질 수 없다.

Bessie는 언제나 끝지점을 향해 달리고 있고, 그녀는 정수시간의 초 안에 끝내고 싶어한다.
(이 정수시간 안에 끝내거나 목표라인을 지난다.)
게다가, 그녀는 결승 지점에서 너무 빨리 달리지 않길 원한다.

Bessie 가 K 미터 달리기를 끝내는 순간, 그녀는 1초에 X ( 1<= X <=10^5) 미터 이하가 되길 원한다.
Bessie 는 N (1<=N=1000) 개의 다른 X 의 값들에 대해 경기를 얼마나 빨리 끝낼 수 있는지 알고 싶어 한다.

입력

첫번째 줄에는 정수 K 와 N 이 입력된다.
다음 N 개의 줄에는 정수 X 가 하나씩 입력된다.

10 5
1
2
3
4
5

출력

각 N 개의 줄에, Bessi가 X 이하의 스피드로 달리기를 끝내도록 K 미터를 달리는데 필요한 최소한의 시간을 출력해라

6
5
5
4
4

입출력 설명

X =1 일 때, 이상적인 solution 은

 

1. 1m/s 로 속도를 올려서 1m 를 달린다.
2. 2m/s 로 속도를 올려서, 2m 를 달린다. 총 3미터를 달렸다.
3. 2m/s 로 속도를 유지한다. 총 5m 를 달린다.
4. 2m/s 로 속도를 유지한다. 총 7m 를 달린다.
5. 2m/s 로 속도를 유지한다. 총 9m 를 달린다.
6. 1m/s 로 속도를 줄인다. 총 10m 를 달린다.

==> 6초 안에 주어진 조건으로 10 m 를 완주 할 수 있다.

풀이

특정 T 초에 x 이하의 속도를 유지해야 하고,
T 초 동안 k 이상 달려야 함.

최대한 많이 달리려면 당연히 점점 속도를 올려야 함

1. 일단 x 까지는 속도를 올림
2. 지금까지 달린 거리가 k 미만인지 확인,
3. k 미만이면, 마지막에 x속도로 달렸다고 가정하고, 일단 그 거리를 더해줌

예시

k = 10, x= 3

그림의 선 아래에 있는거는 초, 위는 1초당 달린 거리를 뜻한다.

1. x=3 이므로 속도가 3m/s 가 되는 순간에 경기가 끝나는 지점에 3m/s 로 달렸다고 가정하고

총 달린 거리에 더해준다.

1 + 2 + 3 + 3 = 9m

2. 목표인 10m 보다 작으므로 속도를 4m/s 로 올려서 달린다.

1 + 2+ 3 + 4 + 3 = 13 > 10 m 를 초과했다!

Bessie 는 5초에 10m 를 완주할 수 있다.

코드

#include <iostream>

using namespace std;
int k;

int solution(int x) {

 int d = 0; //지금까지 달린 거리
 int speed = 0; //현재 속력
 int count = 0; // 달린 초

 // 현재 속력이 x 가 될때까지 일단 올린다.
 for(speed=1; speed<=x && d<k; ++speed) {
     d += speed;
     count++;
 }
 --speed;

 while(d<k) {
     // 마지막 초에 해당 speed 를 더해준다.
     count++;
     d += speed;
     if(d>=k) {
         break;
     }
     count++;
     speed++;
     d += speed;
 }
 return count;

}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;

    cin >> k >> n;
    for(int i=0; i<n; i++) {
        int x;
        cin >> x;
        cout << solution(x) << "\n";
    }
}