백준 12110번 Telefoni

문제 링크입니다: https://www.acmicpc.net/problem/12110

그리디하게 접근하면 O(N)으로 풀 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 시작점으로부터 출발을 합니다.

2. 거리 D 내에 전화가 있으면 해당 전화기로부터 다시 출발합니다.

3. 최대거리(D)를 갔는데도 전화가 없다면 해당 지점에 전화를 설치하고 다시 출발합니다.

#include <iostream>

using namespace std;

 

const int MAX = 300000 + 1;

 

int N, D;

bool phone[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> D;

 

        for (int i = 0; i < N; i++)

                 cin >> phone[i];

 

        int result = 0;

        int cnt = 0;

        for (int i = 0; i < N; i++)

        {

                 if (phone[i])

                         cnt = 0;

                 //최대 길이까지 갔는데도 폰이 없다면 i번째 인덱스에 설치

                 else if (++cnt == D)

                 {

                         result++;

                         cnt = 0;

                 }

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~