[SW Expert Academy 14178번] 1차원 정원 (C++)

문제

SW Expert Academy

---

1치원 정원 문제는 나누기 연산으로 해결할 수 있습니다. 

 

모든 꽃이 한 개 이상의 분무기에서 물을 받을 수 있도록 하기 위해서는 [x - D, x + D] 구간이 겹치지 않도록 물을 주면 됩니다.

1차원 정원이 [1, 2, 3, 4, 5]이고, D가 1인 경우, 첫 번째 분무기는 1번 인덱스에, 두 번째 분무기는 3이나 4번 인덱스에 두면 됩니다. 

 

따라서 필요한 최소한의 분무기 수는 n / (D * 2 + 1)입니다. (D * 2 + 1은 분무기 하나가 물을 줄 수 있는 정원의 길이)

하지만, 만약 n이 (D * 2 + 1)로 나누어 떨어지지 않는 경우, 올림을 해주어 나머지 꽃도 물을 받을 수 있도록 해야합니다.

따라서 최소한의 분무기 수 = ceil((double) n / (D  * 2 + 1)입니다. 

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t, i = 1; cin >> t;
    while(t--){
        int n, d; cin >> n >> d;
        
        cout << "#" << i++ << " " << ceil((double)n / (2 * d + 1)) << "\n";
    }
    return 0;
}