[Algorithm] 🦕白駿2304倉庫ポリゴン
0、問題
N本の柱が一列に並んでいます.柱の幅はすべて1メートルで、高さは違うかもしれません.これらの柱で鉄皮倉庫を作ります.倉庫にはすべての柱が入っています.この倉庫の屋根は次のように作られています.
屋根は水平部分と垂直部分からなり、つながっています.
屋根の水平部分は、ある柱の頂面に接しなければならない.
屋根の垂直部分は、ある柱の側面に接しなければならない.
屋根の縁が落ちる.
雨の時に水が溜まるのを防ぐために、屋根のどの部分も凹んではいけません.
図1は倉庫がそばにある原形を描いている.この図の太い線で示された部分は屋根に相当し、屋根と地面に囲まれた多角形がそばに倉庫が見えた.この多角形を倉庫多角形と呼びましょう.
図1.柱の例
倉庫のボスは、倉庫の多角形面積が最も小さい倉庫を構築したいと思っています.図1の倉庫多角形の面積は98平方メートルであり、この場合は最小の倉庫多角形である.
柱の位置と高さを指定する場合は、最小倉庫の多角形面積を求めるプログラムを作成します.
入力
最初の行は、柱の個数を表す整数Nを与える.Nは1以上1000以下である.次のN行では、各列の1つの柱の左側の位置を表す整数Lと、高さを表す整数Hとがスペースを隔てている.LもHも1以上1000以下です.
しゅつりょく
最初の行は、倉庫のポリゴン面積を表す整数を出力します.
1.アイデア
💡 最大の柱を基準にして、右側と左側に分けます.
💡 左は柱が大きくなった部分のみ、右は柱が小さくなった部分のみを格納します.
💡 最後に一番長い柱を加えます.
💡 例外処理
1)最も長い柱が複数あると幅が重複して増加するという問題がある
→ left.contains(arr[i])右側に重複する柱があることを禁止
2)1のため、右側に一番長い柱が1本しかない場合には、入れないという問題もあります.
→最長柱全体と右側最長柱の幅を求める
2.コア解答
ArrayList<Wood> left = new ArrayList<>();
ArrayList<Wood> right = new ArrayList<>();Wood tmp = left.get(0);
for(int i=1; i<left.size(); i++) {
Wood cur = left.get(i);
sum += Math.abs(cur.x - tmp.x)*tmp.y;
tmp = cur;
}
...
for(int i=N-1; i>=0; i--) {
if(max <= arr[i].y) {
max = arr[i].y;
if(!left.contains(arr[i])) {
right.add(arr[i]);
}
}
}sum += left.get(left.size()-1).y;if(!left.contains(arr[i])) {
right.add(arr[i]);
}sum += Math.abs(left.get(left.size()-1).x-right.get(right.size()-1).x)*right.get(right.size()-1).y;3.コード
import java.io.*;
import java.util.*;
public class BOJ_2304 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
Wood[] arr = new Wood[N];
ArrayList<Wood> left = new ArrayList<>();
ArrayList<Wood> right = new ArrayList<>();
for(int i=0; i< N; i++) {
String[] s = br.readLine().split(" ");
arr[i] = new Wood(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
}
Arrays.sort(arr);
int max = -1;
int sum = 0;
for(int i=0; i<N; i++) {
if(max <= arr[i].y) {
max = arr[i].y;
left.add(arr[i]);
}
}
Wood tmp = left.get(0);
for(int i=1; i<left.size(); i++) {
Wood cur = left.get(i);
sum += Math.abs(cur.x - tmp.x)*tmp.y;
tmp = cur;
}
if(!left.contains(arr[arr.length-1])) {
max = -1;
for(int i=N-1; i>=0; i--) {
if(max <= arr[i].y) {
max = arr[i].y;
if(!left.contains(arr[i])) {
right.add(arr[i]);
}
}
}
tmp = right.get(0);
sum += Math.abs(left.get(left.size()-1).x-right.get(right.size()-1).x)*right.get(right.size()-1).y;
for(int i=1; i<right.size(); i++) {
Wood cur = right.get(i);
sum += Math.abs(cur.x - tmp.x)*tmp.y;
tmp = cur;
}
}
sum += left.get(left.size()-1).y;
System.out.println(sum);
}
static class Wood implements Comparable<Wood>{
int x;
int y;
Wood(int x, int y){
this.x = x;
this.y = y;
}
@Override
public int compareTo(Wood w) {
return this.x - w.x;
};
}
}4.結果
成功
Reference
この問題について([Algorithm] 🦕白駿2304倉庫ポリゴン), 我々は、より多くの情報をここで見つけました https://velog.io/@kha0318/Algorithm-백준-2304-창고-다각형テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol