[SWEA] 7964 부먹왕국의 차원 관문

문제

SWEA 7964 : 부먹왕국의 차원 관문

SW Expert Academy

접근

차원 관문으로부터 거리가 D 이하인 지점까지는 텔레포트가 가능하다. 이때 차원 관문을 최소한으로 설치하여 모든 도시를 드나들 수 있게 만들어주는 문제이다. 여기서 0의 위치와 N + 1의 위치에도 차원 관문이 존재한다는 것을 잊지 말자.

따라서 이는 모든 0이 연속되는 개수(차원 관문이 없는 연속되는 지점)를 D로 나눠준 값들의 합을 구하면 정답을 쉽게 구할 수 있다. 

 

코드

#include <iostream>

using namespace std;

int main() {
    int t, n, d;
    cin>>t;

    for (int i = 0; i < t; i++) {
        cin>>n>>d;
        int count0 = 0, answer = 0, temp;
        for (int j = 0; j < n; j++) {
            cin>>temp;
            if (temp == 0) count0++;
            else {
                answer += count0/d;
                count0 = 0;
            }
        }
        answer += count0/d;
        cout<<"#"<<i+1<<" "<<answer<<"\n";
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study