白峻14719雨水

BOJ 14719

ターゲット:2 Dワールドにブロックがあります.雨が降ったら、街の間に積もった雨を探しに行きます.
条件:2次元世界の縦方向長さHと2次元世界の横方向長さWを与える.(1 ≤ H, W ≤ 500)

ソリューション

この問題は二つの方法で解決できる.重複文を活用する方法とポインタを活用する方法があります.
まず,反復文の手法を用いると,雨水は積み木のない空き空間にしか存在しない.各高さの両端の空白領域をブロックに遭遇するまでチェックし、その空間以外の領域幅を出力します.

#include <stdio.h>
using namespace std;
int block[501][501];
int N, M, ans;

int main() {
	scanf("%d%d",&N,&M);
	for (int i = 0; i < M; i++){
		int a;
		scanf("%d",&a);
		for (int j = 0; j < a; j++){ // block 설치
			block[j][i] = -1;
		}
	}
	for (int i = 0; i < N; i++){
		int next = 0;
		while(!block[i][next]){ 
			block[i][next] = 1;
			next++;
		}
		next = M-1;
		while(!block[i][next]){
			block[i][next] = 1;
			next--;
		}
		for (int j = 0; j < M; j++){
			if (!block[i][j]){
				ans++;
			}
		}
	}
	printf("%d\n",ans);
	
   return 0;
}

次に、ポインタを使用する方法を示します.雨水を形成するには、一番前または一番後ろの石よりも低い石を真ん中に積み上げなければならない.第3段階は高い雨を得ることができる.
1.道路の一番前のブロックの高さである雨水を設置する.
2.最も前のブロック以上に遭遇するまで、これは雨水の幅を増加させる.
3.一番前のブロックより大きいブロックに遭遇した場合、答えは、これは雨の幅を増加させ、そのブロックは一番前のブロックになる.

#include <stdio.h>
#include <vector>
using namespace std;
int N, M, ans;
vector<int> V;

int main() {
	scanf("%d%d",&N,&M);
	for (int i = 0; i < M; i++){
		int a;
		scanf("%d",&a);
		V.push_back(a);
	}
	int tmp = 0, lpt = 0, rpt = M-1;
	for (int i = 0; i < M; i++){
		if (V[lpt] > V[i]){
			tmp += V[lpt]-V[i];
		}
		else{
			ans += tmp;
			tmp = 0;
			lpt = i;
		}
	}
	tmp = 0;
	for (int i = M-1; i >= lpt; i--){
    // 오른쪽에서 부터 빗물이 고이지 못한 왼쪽의 맨앞블록까지
		if (V[rpt] > V[i]){
			tmp += V[rpt]-V[i];
		}
		else{
            ans += tmp;
            tmp = 0;
            rpt = i;
		}
	}
	printf("%d\n",ans);
	
   return 0;
}

以上の方法では,左から,右から,正解を求めることができる.