[BOJ] 백준 11877. 홍수 (Gold IV)

재밌는 문제가 뭐있을까 둘러보다가 발견한 문제.

마침 우리 학교에서 푼 사람이 아무도 없기도 해서 랭작용으로도 좋을 듯 해서 풀어보았다.

문제는 아래와 같다.

https://www.acmicpc.net/problem/11877

11877번: 홍수

문제 해석이 조금 껄끄러울 수 있는데,

쉽게 말해서 1~N까지의 높이로 이루어진 기둥들만으로 히스토그램을 만들되,

양옆 높이가 자신 높이보다 낮을 경우 물이 새므로 불가능하며,

맨 끝쪽에는 물이 없어야 한다는 소리다. 

---

의식의 흐름 및 해설

처음에는 잘 생각이 나지 않아서 N이 3, 4일 때 여러가지 상황을 그려보았다.

그러다가, 양쪽 끝에는 물이 있으면 안되므로 물을 담을 수 있는 양은 1~N-2의 합보다 클 수 없다는 것을 깨달았다.

즉, (N-1)*(N-2)/2보다 x가 클 경우 -1을 출력해준다.

 

그럼 1부터 (N-1)*(N-2)/2까지 모든 경우는 다 될까?

일단 물이 새는 것을 방지하기 위해 물을 담을 수 있는 공간 양 옆에는 가장 높은 기둥 두 개, 즉 N, N-1 높이의 기둥들을 세워두자.

그 기둥들 사이에는 현재 세울 수 있는 기둥 중 가장 높이가 낮은 기둥을 세워보도록 하자. hi + vi를 N-1로 맞춰 물이 새지 않는 한도 내에서 && x를 넘지 않는 한도 내에서 물을 최대한 많이 담자.

그러다가 x가 현재 세울 수 있는 기둥만으로 만족할 수 있는 정도의 양이 되면 그렇게 하도록 하자.

쉽게 말해, 높이를 남은 x에 따라 적절히 조정해서 세우도록 하자는 것이다.

이렇게 하면 1부터 (N-1)*(N-2)/2까지 모든 경우를 만족하도록 세울 수 있다.

 

만약 중복되는 기둥이 존재할까 걱정할 수도 있다.

그러나 x의 범위가 1 ~ (N-1)*(N-2)/2 까지이며, 실제로 남은 기둥들도 1~ N-2까지이므로, 중복되지 않는 한에서 범위 내 모든 x를 만족할 수 있다.

 

참고로 물을 다 채우고, 남은 기둥들을 오름차순으로 세우면 안된다!

그 사이에 물을 담을 수 있기 때문에, 내림차순으로 출력해주든지, 물을 채울 수 없는 형태로 출력해주든지 해야된다.

---

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[1000003];
ll n,x;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>x;
     	// 불가능하게 많은 양을 채우는 요구사항일 경우
	if((n-1)*(n-2)<x*2){
		cout<<-1;
		return 0;
	}
    	// 가장 높은 두 기둥을 세우고
	vis[n]=vis[n-1]=true;
	cout<<n<<" ";
	ll k=x,t=1;
    	// 그 사이에 적절히 기둥을 배치하자.
	while(k){
    		// 채워야할 물의 양이 
        	// 가능한 가장 낮은 기둥으로도 안채워지는 경우
		if(k>=n-1-t){
			cout<<t<<" ";
			k-=(n-1-t);
			vis[t]=true;
			t++;
		}
        	// 가능한 기둥 내에서 만족할 수 있는 경우
		else{
			cout<<(n-1-k)<<" ";
			vis[n-1-k]=true;
			break;
		}
	}
	cout<<n-1<<" ";
    	// 나머지 기둥들 설치
	for(int i=n;i>=1;i--){
		if(!vis[i])cout<<i<<" ";
	}
}

---

오랜만에 재밌는 Constructive, Adhoc 문제를 풀어본 것 같다.

그리디쪽 느낌도 꽤 있는 것 같고.

이런 유형의 문제들도 많이 풀수록 체화가 되려나... 그랬으면 좋겠다.