[C++, 코딩테스트] Softeer : 스마트 물류 with 그리디

 

 

#include<iostream>
#include<vector>
using namespace std;

int main(int argc, char** argv)
{
    int N, K;
    char value;
    vector<char> arr;
    cin >> N >> K;
    for (int i = 0; i < N; i++){
        cin >> value;
        arr.push_back(value);
    }
    int answer = 0;
    for (int i = 0; i < N; i++){
        if (arr[i] == 'H' || arr[i] == 'h')
            continue;
        int left = i - K < 0 ? 0 : i - K;
        int right = i + K >= N ? N - 1 : i + K;
        for (int j = left; j <= right; j++){
            if (arr[j] == 'H'){
                arr[j] = 'h';
                answer++;
                break;
            }
        }
    }
    cout << answer << endl;
    return 0;
}

 

이 문제같은 경우에는 그리디로 푼 문제이다.

 

왼쪽부터 기계를 찾아서 그 기계의 왼쪽에서 가장 먼쪽부터 짚어서 올리면 최대의 개수를 짚을 수 있다.

 

가장 왼쪽부터 짚는 이유는 다음 기계에게 가장 먼 부품을 짚는게 유리하기 때문이다.

 

이런 아이디어만 있다면 금방 풀 수 있는 문제같다.