5357. 터널 속의 기차

터널을 N칸짜리 기차가 지나가는데

적절히 불을 켜놔서 터널을 지나는 어떠한 순간에도 터널안에 최소 하나의 불은 들어와있게 만들고 싶다.

이 때 켜야 하는 최소한의 불 개수를 묻는 문제다.

기차가 터널을 지날 때를 생각해보면

-----------------

[기차][기차][기차]

-----------------

형식인데 첫번째 칸에만 불이 들어와있고 나머지 칸에 들어와있지 않은 경우

-----------------

][기차][기차][기차

-----------------

첫째칸이 마지막에 걸치는 때가 불이 들어와있는 가장 늦은 시간이다.

즉 i번째 칸에 불이 켜져있을때 뒤이어 들어온 칸들의 합이 터널의 길이보다 크거나 같은 순간

마지막으로 들어온 칸에 반드시 불이 켜져있어야 한다는 뜻이다.

이를 적용하는 방법은

1. 입력을 받으면서 현재칸에 불이 켜져있다면 cur = 1로 표시한다. 왜냐하면 현재칸에서 켜진 불은 마지막 1초까지 유효하기 때문이다.

2. 불이 꺼져있다면 cur += [i번째 열차 길이] 를 해준다.

3. 만약 cur > h(터널길이) 라면 현재칸에 불을 켜주고(ans++) 불이 켜졌으므로 다시 cur==1로 돌아간다.

4. 첫번째, 마지막 칸은 무조건 불이 켜져있어야 한다.

-----------------

                [첫번째]

-----------------

       -----------------

[마지막]

       -----------------

이 두가지 경우 때문이다.

#include <iostream>
using namespace std;
 
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    ll tc, n, h, cur, ans, a[100001];
    cin >> tc;
    for (int t = 1; t <= tc; ++t) {
        cin >> n >> h;
        ans = 0;
        cur = 1;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        for (int i = 0, temp; i < n; ++i) {
            cin >> temp;
            if (temp) cur = 1;
            else {
                if (i == 0 || i == n - 1) cur = h + 1;
                else cur += a[i];
            }
            if (cur > h) cur = 1, ans++;
        }
        cout << "#" << t << " " << ans << '\n';
    }
    return 0;
}