맨 첨에 문제 접근 시 메모한 것
-
천천히 생각하면서 메모하니 그냥 구현문제인 것 같은데
-
일단 모든 기둥 폭(너비 = 1)
-
창고에(=지붕에) 모든 기둥 포함되어야
-
지붕은 모두 연결
-
지붕 가장자리는 땅에 닿아야
-
오목하게 들어간 부분( U 이런거 ) 없어야함
-
한 개 기둥의 면적 = y좌표값
-
x축 ++ 하면서
- answer += arr[1] 하는데 그 전에
- if arr[1] = y좌표가 "ny > y"로 다음꺼가 더 클 때 answer += y의 y를 ny로 바꿈
- else 같거나 작으면 answer += y 의 y는 그대로
-
이때 plus해주는 값을 한번만 하는게 아니라
- => 이게 아니었다..!
- 아니!!!!! 맞긴 한데 반쪽짜리 방식이었다..! 한 가지 간과했다!!!!- 가운데 맨 높이 있는 기둥까지는 ㅇㅋ인데,
- 그 다음으로 넘어갈 땐 맨 높은 기둥 높이로 쭉 더해졌음
- 팁 얻고자 구글링 했는데 "스택"을 사용하라 했지만,
- 사실 내게 필요한 나머지 반쪽은
"가운데 가장 높은 기둥을 기준으로 반 반 진행"하는 것이었다
반쪽짜리 접근법으로 풀었던 것 (정답아님)
''' (정답아님!)내가 푼 - 근데 이 경우는 기둥들이 다 붙어있는 경우에만 가능한 답이네 '''
""" 그리고 그림 기준으로 x = 9부터는 이게 안됨 """
answer = 0
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)] # (x, y)
graph.sort() # x좌표 기준 정렬
plus = graph[0][1]
for i in range(1, n): # 이러면 x축 기준으로 하나씩 진행이니까
if plus >= graph[i][1]: # 현재가 다음보다 크거나 같으면
answer += plus
elif plus < graph[i][1]: # 이해를 위해 이렇게 작성
plus = graph[i][1]
answer += plus
print(answer)이 문제에서 도움을 받은 내용
- 출처 : https://kimmeh1.tistory.com/268
- 사실 Stack은 필요 없었음, 도움받은 내용은 아래와 같음
- 한번에 입력 ㄴㄴ, 따로 idx, 높이로 입력(= x, y)
- 높이가 가장 큰 놈의 idx와 높이 저장해둘 것
- 얘를 기준으로 반반 나눠서 브루트폴스 수행
- 배열 사이즈를 그림 전체로 할당했기 때문에, 기둥 다 끝나서 0밖에 없는데 브루트폴스 할 수 있으니까 end_idx도 저장해두기
최종 코드 (no stack)
''' 블로그 참고하여 수행 - 이 유형 핵심은 top을 기준으로 반반 나눠서 수행 '''
answer = 0
n = int(input())
graph = [0] * 1001 # 문제에서 0<=x<=1000 이라 했으므로
max_h = 0
max_h_idx = 0
end_idx = 0
# 그림 모양의 n x n 배열 생성 (입력 받으면서 큰값 저장)
for _ in range(n):
idx, h = map(int, input().split()) # (중요) 이때 x, y가 아니라 index, 높이 이다
graph[idx] = h # (중요) 해당 위치에 높이(=넓이) 저장
# 높이 기준 가장 큰값 저장
if h > max_h:
max_h = h # 가장 높은 애
max_h_idx = idx # 걔의 인덱스(위치)
end_idx = max(end_idx, idx) # 배열의 끝인 1000회까지 가지 않도록 마지막 위치 저장
# 왼쪽 수행 - 내가 생각한 방식은 여기서 통함
plus = graph[0]
for idx in range(1, max_h_idx+1): # 이러면 x축 기준으로 하나씩 진행이니까
if plus < graph[idx]: # next 위치의 높이가 더 큰 값이면 대체
plus = graph[idx] # 왼쪽으로 갈 땐, 다음 위치 높이가 0 이어도 상관없다
answer += plus
# 오른쪽 수행 - 위 내용을 거꾸로!!!!!!!! (중요)
plus = graph[end_idx]
for idx in range(end_idx, max_h_idx, -1): # 이러면 x축 기준으로 하나씩 진행이니까
if plus < graph[idx]: # next 위치의 높이가 더 큰 값이면 대체
plus = graph[idx] # 왼쪽으로 갈 땐, 다음 위치 높이가 0 이어도 상관없다
answer += plus
print(answer)
Do My Best