누적합 문제 3번 질문

2주만에 통과하는 알고리즘 코딩테스트 (2024년)

기억 ( 누적합 )

해결된 질문

작성

텐트 세우기문제를 풀던 중, 가장 높은 높이를 만날때까지 왼쪽에서 오른쪽으로 진행하고, 이후에는 오른쪽에서 가장 높이를 만날때까지 역순으로 누적합 배열 2개를 만들어서 마지막에 더해서 해결하려고 했는데, 입력 예시랑 백준의 반례들 찾아서 집어넣어봤는데 모두 정상적으로 출력되는데, 제출하니 틀렸다고 나오네요. 하루종일 고민했는데 도저히 모르겠어서 질문 드립니다!

#2304 미해결...

TC = int(input())
x_list = []
y_list = []
graph = [0]*1001
for _ in range(TC):
    x, y = map(int, input().split())
    graph[x] = y
    x_list.append(x)
    y_list.append(y)

max_height = max(y_list)
prefix = [0]
check = 0
for i in range(1, max(x_list)):
    prefix.append(max(prefix[i-1], graph[i]))
    if prefix[i] == max_height:
        check = i
        break

suffix = [0]*(max(x_list))
suffix[-1] = graph[max(x_list)]

for i in range(max(x_list)-1, check, -1):
    if suffix[i] == max_height:
        break
    suffix[i-1] = (max(suffix[i], graph[i]))


sum = 0
for i in range(len(prefix)):
    if prefix[i] != 0:
        sum += prefix[i]

for j in range(len(suffix)):
    if suffix[j] != 0:
        sum += suffix[j]

print(sum)

python 코딩-테스트 알고리즘

답변 2

코딩 센세

지식공유자

답변이 늦어서 죄송합니다! 혹시 해당 문제 해결하셨을까요?

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

gd12091님께서 언급하신 문제는 “텐트 세우기” 문제로, 여러 기둥의 높이 값을 통해 전체 면적을 구하는 작업이 필요합니다. 주어진 코드에서 몇 가지 실수를 확인하고 간단하게 최적화할 수 있는 방법을 안내해드리겠습니다.

기존에 누적합 배열(prefix, suffix)을 구별하여 값을 계산하는 방식이지만, 누적합 문제를 좀 더 직관적으로 해결하기 위해서는 배열을 두 번 스윕(sweep) 하면서 최대 높이를 찾고 면적을 구하는 것이 효율적입니다.

우선, 아래 링크의 답변들을 확인해보세요. 이 질문들과 답변들이 gd12091님의 문제를 해결하는 데 도움을 줄 것입니다:

두 번째 링크에서는 누적합을 통해 효율적인 계산을 다루고 있으니, 참고해보세요.

아래는 코드를 수정한 예시입니다. 최적화된 누적합 방법을 통해 문제를 해결하는 방식으로 작성되었습니다:

import sys
input = sys.stdin.read

TC = int(input())
pillars = [list(map(int, input().split())) for _ in range(TC)]

pillars.sort()
max_height = 0
max_idx = 0
for i in range(TC):
    if pillars[i][1] > max_height:
        max_height = pillars[i][1]
        max_idx = i

area = 0
left_max = 0
for i in range(max_idx + 1):
    left_max = max(left_max, pillars[i][1])
    if i+1 < TC and pillars[i+1][0] > pillars[i][0]:
        area += left_max * (pillars[i+1][0] - pillars[i][0])

right_max = 0
for i in range(TC - 1, max_idx, -1):
    right_max = max(right_max, pillars[i][1])
    if i-1 >= 0 and pillars[i][0] > pillars[i-1][0]:
        area += right_max * (pillars[i][0] - pillars[i-1][0])

area += max_height
print(area)

이 코드는 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 2번 스윕하면서 최대 높이를 찾고 해당 높이 기준으로 누적합을 구해 전체 면적을 계산합니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

누적합 문제 3번 질문