(SWEA c++)7964. 부먹왕국의 차원 관문

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWuSgKpqmooDFASy&categoryId=AWuSgKpqmooDFASy&categoryType=CODE

SW Expert Academy

핵심은 0번째와 N + 1은 무조건 1이라는 것이다.

그래서 시작 인덱스를 -1로 하였고, i < N - 1이면 while문을 돌도록 설정하였다.

 

우선 i번째 부터 D 거리 이내에 1이 있는지 확인을 해야한다.

만약 해당 인덱스 위치에 1이 있다면 i += j를 해주고, check = true로 바꿔주어 카운팅을 하지 않도록 한다.

D거리 이내에 1이 없다면 카운팅 + 1을 해주고, 인덱스 또한 + D 를 해주어 이동시켜주도록 한다.

 

이렇게 하면 답을 구할 수 있다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> v(300001, 0);

int main(void)
{
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        int N, D, ans = 0, i = -1;
        
        cin >> N >> D;
        for(int i = 0; i < N; i++)
        	cin >> v[i];
        
        while(i < N - 1)
        {
            bool check = false;
            
            for(int j = 1; j <= D; j++)
            {
               if(i + j < N && v[i + j])
               {
                   check = true;
                   i += j;
                   break;
               }
            }
            if(!check)
            {
                ans++;
            	i += D;
            }
        }
        cout << "#" << tc << " " << ans << endl;
    }
    return 0;
}