NYPC 2021 예선 | 폭탄 터트리기 풀이

[문제]

 

다오는 폭탄 터트리기 게임을 하려고 한다. 게임에서는 폭탄 N개가 좌우로 한 줄로 주어진다. 왼쪽에서 i번째 폭탄은 자연수 값 Ai​Ai를 가진다.

6개 폭탄 예시

값이 X인 폭탄을 클릭하면 그 폭탄과, 폭탄에 연속적으로 인접하면서 값이 X 이상 X+K 이하인 것들이 모두 터진다. 예를 들어, 위 그림에서 K=3이라고 하고, 왼쪽에서 세 번째 폭탄을 터트린 경우 아래와 같은 상황이 된다.

폭탄이 터진 후 예시

위 그림처럼 폭탄이 터진 자리는 그대로 남아 있어서, 처음에 인접하지 않았던 폭탄의 쌍은 그 이후에도 인접하지 않다.

폭탄을 클릭하는 횟수가 많을수록 점수가 줄어들어서, 다오는 폭탄을 최소 횟수로 클릭해서 게임을 해결하고 싶다.

주어진 폭탄들과 K의 값을 입력으로 받아 최소 클릭 횟수를 계산하는 프로그램을 작성하라.

 

 

[입력 형식]

 

첫 줄에 폭탄의 개수를 나타내는 정수 N과 폭탄의 범위를 나타내는 정수 K가 공백으로 구분되어 주어진다. (1≤N≤300000; 0≤K≤1000000000)

둘째 줄에 N개의 정수 A1.....AN​이 공백으로 구분되어 주어진다. (1≤Ai​≤1000000000)

 

 

[출력 형식]

 

최소의 선택 횟수를 출력한다.

 

 

[해설]

 

클릭 횟수가 최소가 되어야 한다, 라는 조건을 구간합 개념과 섞어서 생각해보겠습니다.

문제에서 "값이 X인 폭탄을 클릭하면 그 폭탄과, 폭탄에 연속적으로 인접하면서 값이 X 이상 X+K 이하인 것들이 모두 터진다"라며 구간합에 대한 힌트를 주고 있습니다.

위의 힌트를 바탕으로 생각해보면, 이 문제는 입력받은 배열 arr에서 구간의 최솟값과 최댓값의 차이가 k 이하인 x개의 구간을 만들 때, x의 최솟값을 구하는 문제라는 것을 알 수 있습니다.

앞에서부터 차례대로 스위핑을 돌리며 그리디 하게 해결하면 문제가 풀리게 됩니다.

 

 

[C/C++ 코드]

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int arr[300001],n,k,res=1,mn=1e9,mx=-1e9;

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        mx=max(mx,arr[i]);
        mn=min(mn,arr[i]);
        if(mx-mn>k){
        	res++;
			mn=mx=arr[i];
		}
    }
    cout<<res;
}