[Codeforces 1061B] Views Matter

[Codeforces 1061B] Views Matter

Problem - B - Codeforces

문제 설명 : 

i번째에 a[i]층 만큼 쌓인 블럭들이 주어진다. 제거할 수 있는 블럭의 최대 개수를 구하는데, 제거 하기 전과 후의 위에서 본 모습과 옆에서 본 모습에는 차이가 없어야 한다. 참고로 중력은 고려하지 않아서 아래에 있는 블럭을 제거해도 위에 있는 블럭을 떨어지지 않는다고 가정한다.

 

풀이 : 

일단 오름차순으로 정렬을 한다. 그리고 처음에는 각 블럭들을 1개만 제외하고 나머지 (a[i]-1)개의 블럭을 모두 제거한다고 가정한다( ans+=a[i]-1 ). 여기까지만 생각하면 높이가 1 2 3 4 와 같이 높이가 1씩 차이나는 블럭 배치는 정답을 구할 수 있으나, 1 5 와 같은 배치는 답이 다르게 나온다. 이 경우를 처리하기 위해서 나는 별도의 h라는 변수를 둘 것이다. h의 의미는 '현재까지 옆에서 봤을 때 h층까지 커버했음'이라는 의미이다. 위 알고리즘에서 각 블럭들을 1개만 남겼으므로 h는 1씩 증가할 것이다. 그러다가 맨 마지막까지 다 돌았을 때 h의 크기가 모든 a[i]중에 가장 큰 값인 max_h의 크기보다 작다면 그 둘의 차이인 (max_h-h)만큼의 높이는 커버하지 못했다는 의미이다. 따라서 그 값만큼은 다시 ans에서 빼주어야 한다.

 

주의할 점 : 

-

 

배운 점 :

난이도에 비해 푸는 데 시간이 엄청 오래 걸린 문제였다. 처음에 map을 사용한 풀이는 왜 틀렸는지는 아직도 모르겠다. 

 

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
// #define SIZE
// #define IMP
// #define INF
// const int MOD=
struct S{
	int a,b;

	S(){}
	S(int _a,int _b){
		a=_a;
		b=_b;
	}

	const bool operator<(const S &o) const{
		return a<o.a;
	}
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
// map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
const int SIZE=100009;

int arr[SIZE];
int main(){
	int n,m;	scanf("%d %d",&n,&m);

	int max_h=0;
	for(int i=1 ; i<=n ; i++){
		scanf("%d",&arr[i]);
		max_h=max(max_h,arr[i]);
	}

	sort(arr+1,arr+1+n);

	ll ans=0;
	int h=0;
	for(int i=1 ; i<=n ; i++){
		if(arr[i]>h) h++;
		ans+=arr[i]-1;
	}
	if(max_h>h) ans-=max_h-h;
	printf("%lld\n",ans);

	return 0;
}