N ๊ฐ์ ๋ง๋ ๊ธฐ๋ฅ์ด ์ผ๋ ฌ๋ก ์ธ์์ ธ ์๋ค. ๊ธฐ๋ฅ๋ค์ ํญ์ ๋ชจ๋ 1 m์ด๋ฉฐ ๋์ด๋ ๋ค๋ฅผ ์ ์๋ค. ์ด ๊ธฐ๋ฅ๋ค์ ์ด์ฉํ์ฌ ์์ฒ ๋ก ๋ ์ฐฝ๊ณ ๋ฅผ ์ ์ํ๋ ค๊ณ ํ๋ค. ์ฐฝ๊ณ ์๋ ๋ชจ๋ ๊ธฐ๋ฅ์ด ๋ค์ด๊ฐ๋ค. ์ด ์ฐฝ๊ณ ์ ์ง๋ถ์ ๋ค์๊ณผ ๊ฐ์ด ๋ง๋ ๋ค.
์ง๋ถ์ ์ํ ๋ถ๋ถ๊ณผ ์์ง ๋ถ๋ถ์ผ๋ก ๊ตฌ์ฑ๋๋ฉฐ, ๋ชจ๋ ์ฐ๊ฒฐ๋์ด์ผ ํ๋ค.
์ง๋ถ์ ์ํ ๋ถ๋ถ์ ๋ฐ๋์ ์ด๋ค ๊ธฐ๋ฅ์ ์๋ฉด๊ณผ ๋ฟ์์ผ ํ๋ค.
์ง๋ถ์ ์์ง ๋ถ๋ถ์ ๋ฐ๋์ ์ด๋ค ๊ธฐ๋ฅ์ ์๋ฉด๊ณผ ๋ฟ์์ผ ํ๋ค.
์ง๋ถ์ ๊ฐ์ฅ์๋ฆฌ๋ ๋ ์ ๋ฟ์์ผ ํ๋ค.
๋น๊ฐ ์ฌ ๋ ๋ฌผ์ด ๊ณ ์ด์ง ์๋๋ก ์ง๋ถ์ ์ด๋ค ๋ถ๋ถ๋ ์ค๋ชฉํ๊ฒ ๋ค์ด๊ฐ ๋ถ๋ถ์ด ์์ด์ผ ํ๋ค.
๊ทธ๋ฆผ 1์ ์ฐฝ๊ณ ๋ฅผ ์์์ ๋ณธ ๋ชจ์ต์ ๊ทธ๋ฆฐ ๊ฒ์ด๋ค. ์ด ๊ทธ๋ฆผ์์ ๊ตต์ ์ ์ผ๋ก ํ์๋ ๋ถ๋ถ์ด ์ง๋ถ์ ํด๋น๋๊ณ , ์ง๋ถ๊ณผ ๋ ์ผ๋ก ๋๋ฌ์ธ์ธ ๋ค๊ฐํ์ด ์ฐฝ๊ณ ๋ฅผ ์์์ ๋ณธ ๋ชจ์ต์ด๋ค. ์ด ๋ค๊ฐํ์ ์ฐฝ๊ณ ๋ค๊ฐํ์ด๋ผ๊ณ ํ์.
๊ทธ๋ฆผ1 . ๊ธฐ๋ฅ๊ณผ ์ง๋ถ(๊ตต์ ์ )์ ์
์ฐฝ๊ณ ์ฃผ์ธ์ ์ฐฝ๊ณ ๋ค๊ฐํ์ ๋ฉด์ ์ด ๊ฐ์ฅ ์์ ์ฐฝ๊ณ ๋ฅผ ๋ง๋ค๊ธฐ๋ฅผ ์ํ๋ค. ๊ทธ๋ฆผ 1์์ ์ฐฝ๊ณ ๋ค๊ฐํ์ ๋ฉด์ ์ 98 ใก์ด๊ณ , ์ด ๊ฒฝ์ฐ๊ฐ ๊ฐ์ฅ ์์ ์ฐฝ๊ณ ๋ค๊ฐํ์ด๋ค.
๊ธฐ๋ฅ๋ค์ ์์น์ ๋์ด๊ฐ ์ฃผ์ด์ง ๋, ๊ฐ์ฅ ์์ ์ฐฝ๊ณ ๋ค๊ฐํ์ ๋ฉด์ ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ ์ค์๋ ๊ธฐ๋ฅ์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์ N์ด ์ฃผ์ด์ง๋ค. N์ 1 ์ด์ 1,000 ์ดํ์ด๋ค. ๊ทธ ๋ค์ N ๊ฐ์ ์ค์๋ ๊ฐ ์ค์ ๊ฐ ๊ธฐ๋ฅ์ ์ผ์ชฝ ๋ฉด์ ์์น๋ฅผ ๋ํ๋ด๋ ์ ์ L๊ณผ ๋์ด๋ฅผ ๋ํ๋ด๋ ์ ์ H๊ฐ ํ ๊ฐ์ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. L๊ณผ H๋ ๋ ๋ค 1 ์ด์ 1,000 ์ดํ์ด๋ค.
์ถ๋ ฅ
์ฒซ ์ค์ ์ฐฝ๊ณ ๋ค๊ฐํ์ ๋ฉด์ ์ ๋ํ๋ด๋ ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ก ๊ฐ์ฅ ํฐ ๊ธฐ๋ฅ์ ๊ธฐ์ค์ผ๋ก ์ค๋ฅธ์ชฝ๊ณผ ์ผ์ชฝ์ ๋๋
๐ก ์ผ์ชฝ์ ๊ธฐ๋ฅ์ด ์ปค์ง๋ ๊ตฌ๊ฐ๋ง ์ ์ฅํ๊ณ ์ค๋ฅธ์ชฝ์ ๊ธฐ๋ฅ์ด ์์์ง๋ ๊ตฌ๊ฐ๋ง ์ ์ฅํจ
๐ก ๋ง์ง๋ง์ผ๋ก ์ ์ผ ๊ธด ๊ธฐ๋ฅ์ ๋ํด์ค
๐ก ์์ธ์ฒ๋ฆฌ
1) ์ ์ผ ๊ธด ๊ธฐ๋ฅ์ด ์ฌ๋ฌ ๊ฐ ์ผ ๋, ๋์ด๊ฐ ์ค๋ณต๋์ด์ ๋ํด์ง๋ ๋ฌธ์ ์ ๋ฐ์
โ left.contains(arr[i])๋ฅผ ํ์ฌ right์ ์ค๋ณต๋ ๊ธฐ๋ฅ์ด ๋ค์ด๊ฐ์ง ๋ชปํ๊ฒ ํจ
2) 1๋ก ์ธํด, right์ ์ ์ผ ๊ธด ๊ธฐ๋ฅ์ด ํ๋์ผ ๋๋ ๋ค์ด์ค์ง ๋ชปํ๋ ๋ฌธ์ ์ ์ด ๋ฐ์
โ ์ ์ฒด์์ ๊ฐ์ฅ ๊ธด ๊ธฐ๋ฅ๊ณผ ์ค๋ฅธ์ชฝ์์ ๊ฐ์ฅ ๊ธด ๊ธฐ๋ฅ ์ฌ์ด์ ๋์ด๋ฅผ ๊ตฌํด์ค
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;
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;
};
}
}
์ฑ๊ณตโจ