728x90
위의 그림을 보게 되면 어떻게 구해야 할지 감이 오는 문제.
앞에서부터 시작해서 점점 커지는 기둥만 넣고 반대로 뒤에서부터 시작해서 점점 커지는 기둥을 넣고 계산하면 끝!
문제 풀이
- 기둥의 시작위치가 랜덤 하기 때문에 class를 하나 만들어서 시작 위치 순으로 정렬
- 가작 작은 위치부터 시작해서 증가하면서 커지는 기둥만 ArrayList에 넣기 그림에서는 2
- 반대로 가장 높은 위치에서 시작해서 감소하면서 커지는 기둥만 ArrayList에 넣기 그림에서는 15
- Arraylist에서 이전값의 h에다가 사이의 값을 곱해서 더하기
- 마지막으로 가장높은 위치 한번 더 더해주기
주의 사항!
이렇게 해주게 되면
이렇게 색칠한 부분이 들어가지 않는다. 처음부터 시작한 것이 6,8 이 끝이고 뒹서부터 시작한 것이 8,8 이기 때문이다.
그러므로 (뒤에서 계산한 끝의 위치)- (처음부터 계산한 끝의 위치)*최대 높이 를 더해줘야 한다.
전체 코드
더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main{
public static class cols implements Comparable<cols>{
int x;
int h;
public cols(int x, int h) {
super();
this.x = x;
this.h = h;
}
@Override
public int compareTo(cols o) {
// TODO Auto-generated method stub
return this.x-o.x;
}
}
static int n;
static ArrayList<cols> divr,divl,num;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
num=new ArrayList<cols>();
divr=new ArrayList<cols>();
divl=new ArrayList<cols>();
for(int i=0;i<n;i++) {
StringTokenizer st=new StringTokenizer(br.readLine());
num.add(new cols(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
}
Collections.sort(num);
for(int i=0;i<n;i++) {
if(divr.isEmpty()||divr.get(divr.size()-1).h<num.get(i).h) {
divr.add(num.get(i));
}
}
for(int i=n-1;i>=0;i--) {
if(divl.isEmpty()||divl.get(divl.size()-1).h<num.get(i).h) {
divl.add(num.get(i));
}
}
int result=0;
for(int i=1;i<divr.size();i++) {
result+=(divr.get(i).x-divr.get(i-1).x)*divr.get(i-1).h;
}
for(int i=1;i<divl.size();i++) {
result+=(divl.get(i-1).x-divl.get(i).x)*divl.get(i-1).h;
}
result+=(divl.get(divl.size()-1).x-divr.get(divr.size()-1).x)*divr.get(divr.size()-1).h;
result+=divr.get(divr.size()-1).h;
System.out.println(result);
}
}
'IM대비' 카테고리의 다른 글
백준 10163 <색종이> (0) | 2020.09.24 |
---|---|
백준 2559 <수열> (0) | 2020.09.23 |
백준 2116 <주사위쌓기> (0) | 2020.09.21 |
백준 2628 <종이자르기> (0) | 2020.09.21 |
백준 1244 <스위치 켜고 끄기> (0) | 2020.09.21 |