문제
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
- 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
- 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
- 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
- 지붕의 가장자리는 땅에 닿아야 한다.
- 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
출력
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
예제 입력 1
7
2 4
11 4
15 8
4 6
5 3
8 10
13 6
예제 출력 1
98
🎨 나의 풀이
import sys
input=sys.stdin.readline
N=int(input()) # 기둥의 개수
dict={}
for n in range(N) :
pos, height=map(int, input().split())
dict[pos]=height
sort_dict=sorted(dict) # 정렬된 딕셔너리 키가 담긴 리스트
end=max(dict, key=lambda x : dict[x]) # 가장 긴 기둥이 있는 위치
total=0
max_height = 0
start=sort_dict[0]
for i in range(start, end+1) :
if i in dict :
if dict[i] > max_height :
max_height=dict[i]
total+=max_height
max_height=0
start=sort_dict[-1]
for i in range(start, end, -1) :
if i in dict :
if dict[i] > max_height :
max_height=dict[i]
total+=max_height
print(total)가장 긴 기둥을 기준으로 왼쪽과 오른쪽의 넓이를 구한다.
왼쪽은 기둥의 시작 위치에서 가장 긴 기둥까지, 오른쪽은 끝에서 가장 긴 기둥 전까지다.
딕셔너리에 키는 위치, 값은 높이를 넣었다.
딕셔너리를 key순으로 오름차순 정렬한 리스트 sort_dict를 얻었다.
기둥이 없는 공간은 지금까지의 최대 높이를 사용한다.(수평을 이루어야 하기 때문에)
// 실패
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine()); // 기둥의 개수
StringTokenizer st=new StringTokenizer("");
int[] arr=new int[1001];
int ans=0;
int max_height=0;
int last_pos=0;
int end=0;
for(int n=0; n<N; n++){
st=new StringTokenizer(br.readLine());
int L=Integer.parseInt(st.nextToken()); // 위치
int H=Integer.parseInt(st.nextToken()); // 높이
arr[L]=H;
if(max_height <= H){
max_height=H;
end=L;
}
}
Stack<Integer> stack=new Stack<>();
stack.add(0);
for(int l=0; l<=end; l++){
if(!stack.isEmpty() && arr[stack.peek()] < arr[l]){
int top=stack.pop();
ans+=(l-top)*arr[top];
stack.add(l);
}
}
stack.clear();
stack.add(0);
for(int r=last_pos; r>=end; r--){
if(!stack.isEmpty() && arr[stack.peek()] <= arr[r]){
int top=stack.pop();
ans+=(top-r)*arr[top];
stack.add(r);
}
}
while(!stack.isEmpty()){
ans+=arr[stack.pop()];
}
System.out.println(ans);
}
}입력이 기둥의 위치순으로 주어지는게 아니라서ㅠㅠ
가장 높은 기둥의 인덱스 end를 구하는 게 문제다.
가장 높은 기둥이 여러 개면 end는 그중 왼쪽 인덱스여야 한다.
indexOf를 쓸려고 했는데 wrapper타입이어야 한다.
🐩 다른 사람 풀이
import sys
n=int(sys.stdin.readline().strip())
l=[0 for _ in range(1001)]
m=0
for i in range(n) : # 입력 받으면서 가장 높은 기둥의 값, 인덱스 찾기
a, b=map(int, sys.stdin.readline().strip().split())
if l[a] < b : l[a]=b
if b > m :
m=b
mi=a
ans=0
m=0
for i in range(0, mi) :
if l[i] > m :
m=l[i]
ans+=m
m=0
for i in range(1000, mi-1, -1) :
if l[i] > m :
m=l[i]
ans+=m
print(ans)기둥의 위치, 높이를 입력 받으면서 가장 높은 기둥을 찾는다.
입력 다 받은 후에 찾는 것 보다는 효율이 좋다.
왼쪽은 0부터 가장 높은 기둥 인덱스 전까지, 오른쪽은 1000부터 높은 기둥 인덱스까지다.
나는 마지막 기둥의 위치를 찾았는데 이 풀이는 문제의 입력 제한 조건 1000까지로 했다.
from sys import stdin
read=lambda : stdin.readline().rstrip()
n=int(read())
h=[0]*1001
end=0
for i in range(n) :
x, y=map(int, read().split())
h[x]=y
end=max(end, x) # 마지막 기둥 위치
highest=h.index(max(h)) # 가장 높은 기둥 인덱스
stack=[0]
res=0
for i in range(highest+1) :
if stack and h[stack[-1]] < h[i] :
tx=stack.pop()
res+=(i-tx)*h[tx]
stack.append(i)
stack=[0]
for i in range(end, highest-1, -1) :
if stack and h[stack[-1]] <= h[i] :
tx=stack.pop()
res+=(tx-i)*h[tx]
stack.append(i)
while stack :
res+=h[stack.pop()]
print(res)stack
리스트 stack에 인덱스를 담는다.
이전 기둥보다 더 높은 기둥이 나타나면 스택에서 pop한다.
현재 위치에서 pop한 인덱스까지의 높이는 (i-tx)*h[tx]다.
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine()); // 기둥의 개수
int[] map=new int[1001];
int left=1000;
int right=1;
for(int i=0; i<N; i++){
StringTokenizer st=new StringTokenizer(br.readLine());
int x=Integer.parseInt(st.nextToken()); // 위치
int height=Integer.parseInt(st.nextToken()); // 높이
map[x]=height;
if(x < left) {
left=x;
}
if(x > right){
right=x;
}
}
// 왼쪽, 오른쪽에서 시작해서 면적 저장
int[] leftMap=new int[right+1];
int[] rightMap=new int[right+2];
// 왼쪽에서 시작한 면적 구하기
for(int i=left; i<=right; i++){
// 이전 영역보다 크면 영역의 크기 변경
leftMap[i]=Math.max(leftMap[i-1], map[i]);
}
// 오른쪽에서 시작한 면적 구하기
for(int i=right; i>=left; i--){
rightMap[i]=Math.max(rightMap[i+1], map[i]);
}
int answer=0;
for(int i=left; i<=right; i++){
answer+=Math.min(leftMap[i], rightMap[i]);
}
System.out.println(answer);
}
}왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 위치별로 높이를 구한다.
위치 i의 높이는 왼쪽[i]와 오른쪽[i]중 더 작은 높이다.
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine()); // 기둥의 개수
int[] height=new int[1001];
int left=Integer.MAX_VALUE;
int right=Integer.MIN_VALUE;
int tallest=Integer.MIN_VALUE;
int tallestIdx=0;
for(int i=0; i<N; ++i){
StringTokenizer st=new StringTokenizer(br.readLine());
int L=Integer.parseInt(st.nextToken());
int H=Integer.parseInt(st.nextToken());
left=Math.min(left, L);
right=Math.max(right, L);
height[L]=H;
if(H > tallest){
tallest=H;
tallestIdx=L;
}
}
int sum=0;
int hmax=height[left];
for(int i=left; i<=tallestIdx; ++i){
hmax=Math.max(hmax, height[i]);
sum+=hmax;
}
hmax=height[right];
for(int i=right; i>tallestIdx; --i){
hmax=Math.max(hmax, height[i]);
sum+=hmax;
}
System.out.println(sum);
}
}입력 받으면서 기둥의 시작점 left, 마지막 기둥 right를 구한다.
왼쪽에서 가장 높은 기둥까지, 오른쪽에서 가장 높은 기둥전까지 각각의 넓이를 더한다.
이전 최고값 hmax와 현재 height[i]를 비교해서 더 큰값을 sum에 더한다.
문제 출처 👉 백준
'coding test' 카테고리의 다른 글
| [파이썬, Java] 징검다리 건너기 (0) | 2021.10.28 |
|---|---|
| [파이썬, Java] 14719. 빗물 (0) | 2021.10.22 |
| [파이썬, Java] 9205. 맥주 마시면서 걸어가기 (0) | 2021.10.20 |
| [파이썬, Java] 2493. 탑 (0) | 2021.10.19 |
| [파이썬, Java] 16928. 뱀과 사다리 게임 (0) | 2021.10.19 |