# [Bronze II] 하늘에서 떨어지는 $N$개의 별 [문제 링크](https://www.acmicpc.net/problem/33674) ## 문제 설명 <p>당신은 $D$일 동안 하떨별 마을의 환경 관리자로 일하게 되었다. 하떨별 마을은 하늘에서 별이 떨어지기로 유명한 마을로 별들은 다음과 같은 규칙으로 떨어진다.</p> <ul> <li>별이 떨어지는 위치는 $N$개의 점이다. 점은 순서대로 $1$, $2$, $cdots$, $N$의 번호를 갖는다.</li> <li>첫날 낮에 모든 점에 쌓인 별의 개수는 각각 $0$개다.</li> <li>$i$번 점에는 매일 밤 $s_i$개의 별이 떨어진다. $(1 le i le N)$</li> </ul> <p>별이 많이 쌓이면 폭발할 수 있기 때문에 쌓인 별을 청소해야 한다.</p> <ul> <li>임의의 $i$번 점에 쌓인 별의 개수가 $K$개를 초과하면 해당 점의 별들이 폭발한다. $(1 le i le N)$</li> <li>별이 떨어지는 밤이 되기 전, 낮에 청소 작업을 할 수 있다. 청소 작업을 진행하면 모든 점에 쌓인 별이 $0$개가 된다.</li> </ul> <p>여러분은 $D$일 동안 떨어진 별이 폭발하지 않게 관리해야 한다. $D$일 동안 별이 폭발하지 않도록 하는 최소 청소 횟수를 구해보자.</p> ## 입력 <p>첫 번째 줄에 정수 $N$, $D$, $K$가 공백으로 구분되어 주어진다.</p> <p>두 번째 줄에 정수 $s_1, s_2, cdots, s_N$이 공백으로 구분되어 주어진다.</p> ## 출력 <p>첫 번째 줄에 $D$일 동안 별이 폭발하지 않도록 할 수 있는 최소 청소 횟수를 출력한다.</p> ## 풀이 #### 이 문제에선 N개의 지점에 S_i만큼의 별이 떨어지고, 그 별을 K가 넘지 않도록 청소를 해야합니다. 하지만 맨 처음에 쌓인 별의 양은 모두 0이기에 최대 S_i만 고려하여 풀면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int N, D, K; cin >> N >> D >> K; int maxS=0; for(int i=0;i<N;i++) { int s; cin >> s; maxS = max(maxS, s); } int clearCnt=0, cur=0; while(D--) { if(cur+maxS>K) { clearCnt++; cur=0; } cur += maxS; } cout << clearCnt; } ```