32867번 : 피아노 [C++]

문제 링크

성공 여부 (걸린 시간): 성공 (23분)

아이디어

문제를 읽다보니 그때 그때 상황마다 최선의 선택을 취하므로 그리디문제임을 알 수 있었고 그리디하게 풀어보았다.

 

로직은 손의 시작과 끝 지점을 갱신해주면서 범위를 벗어나는 경우에 갱신과 카운트를 해주면 됨

 

일단 나는 손의 시작과 끝 지점을 min_max pair를 통해서 관리해줬다. 

초기와 각 손을 옮기고 난 후 첫 시작은 옮기거나 시작했던 건반으로 초기화를 해준다.

예) 3으로 시작했다? {3, 3}, 만약 7에서 옮겨야한다? {7, 7} 

 

크게 생각할 분기는 2가지이다.

1. 새로 입력받은 건반이 현재 손의 최대값보다 큰 경우

2. 새로 입력받은 건반이 현재 손의 최솟값보다 작은 경우

최소 이상, 최대 이하인 경우에는 넘어가면 된다. (왜냐면 손을 옮길 필요가 없으니까!)

 

1. 새로 입력받은 건반이 현재 손의 최대값보다 큰 경우

최솟값과 새로입력 받은 건반의 차이가 K이상이라면 손을 옮겨야 함으로 갱신을 진행해줌.

 

2. 새로 입력받은 건반이 현재 손의 최솟값보다 작은 경우

최대값과 새로입력 받은 건반의 차이가 K이상이라면 손을 옮겨야 함으로 갱신을 진행해줌.

 

풀이 코드

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, K;
    cin >> N >> K;
    pair<int, int> min_max;
    int first_num;
    cin >> first_num;

    min_max.first = first_num;
    min_max.second = first_num;

    int answer = 0;
    N--;
    K--;
    while (N-- != 0) {
        int a;
        cin >> a;
        // 최대값보다 큰 경우
        if (a > min_max.second) {
            if (a - min_max.first > K) {
                answer++;
                min_max = { a, a };
            }
            else {
                min_max.second = a;
            }
        }
        //최소값보다 작은 경우
        else if (a < min_max.first) {
            if (min_max.second - a > K) {
                answer++;
                min_max = { a, a };
            }
            else {
                min_max.first = a;
            }
        }
    }
    cout << answer;
    return 0;
}