白峻14719雨水
21805 ワード
マジシャンです
2次元の世界には積み木がいっぱい積まれている.雨が降ると、積み木の間に雨が溜まります.
雨がひどく降った.水たまりの雨水の総量はいくらですか?
アルゴリズムのヒントを見て、実装、シミュレーションと書いてあります.何でも書けば解ける.
最初に考えられる方法は,図のような2次元配列を探索する際に,ブロックとブロックの間の白空間の個数だけを数えることである.
1.1行をナビゲートするときに黒いブロックが表示された場合は、後からカウントします。
2.黒い塊の連続出現に対応
以上の2つの要因を考慮して,コードを記述した.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_14719_빗물 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int H = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
boolean flag = false; //흰 블록을 세기위한 스위치 true면 셀 수 있다.
int[] arr = new int[W];
st = new StringTokenizer(br.readLine(), " ");
int maxH = 0;
for (int i = 0; i < W; i++) {
arr[i] = Integer.parseInt(st.nextToken());
maxH = Math.max(maxH, arr[i]);
//주어진 블록들의 높이가 H보다 낮을수도 있으므로 최대 높이 블록 저장
}
int sum = 0;
//최대 높이 블록의 행 부터 검사 시작
for (int i = H - maxH; i < H; i++) {
int cnt = 0;
flag = false;
for (int j = 0; j < W; j++) {
//검정색 블록이라면 흰 블록 세야하므로 flag = true;
//무조건 sum에 더해주고 nt는 0으로 초기화
if (i >= (H - arr[j])) {
flag = true;
sum += cnt;
cnt = 0;
continue;
}
//flag가 true면 흰 블록 개수를 셀 수 있다.
if (flag)
cnt++;
}
}
System.out.println(sum);
}
}
非常に簡単な解法です...次に、最大高さのブロックのローインデックスから開始し、時間を最大限に節約します.速度も136 msで思ったより速かったです.第2の考え方は,最高ブロックの位置(maxh)に基づいて両側からmaxhにナビゲートし,同時に白空間を計算することである.
水が溜まるかどうかをチェックすればいいです。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_14719_빗물2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int H = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
int[] arr = new int[W];
st = new StringTokenizer(br.readLine(), " ");
int maxH = 0;
int posi = 0;
for (int i = 0; i < W; i++) {
int s = Integer.parseInt(st.nextToken());
if (maxH < s) {
maxH = s;
posi = i; // 가장 긴 블록의 길이와, 위치 저장
}
arr[i] = s;
}
int sum = 0;
int a = arr[0];//기준을 정해줌
int b = arr[W - 1];
for (int i = 1; i < posi; i++) {
if (a > arr[i]) {
// 기준보다 작으면 물이 고일 수 있으므로 값을 더해준다
sum += a - arr[i];
} else {
// 기준보다 크면 물이 고일 수 없으므로 기준을 갱신
a = arr[i];
}
}
for (int i = W - 1; i > posi; i--) {
if (b > arr[i]) {
sum += b - arr[i];
} else {
b = arr[i];
}
}
System.out.println(sum);
}
}
この方式は132 msに達するより速い.コテ通まではまだ遠いですね~~元気を出して、ピナコ
Reference
この問題について(白峻14719雨水), 我々は、より多くの情報をここで見つけました https://velog.io/@fufru/백준-14719-빗물テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol