두 개의 정수 n과 h, 그리고 m개의 삼중항(triplet)으로 이루어진 배열 T가 주어집니다. 여기서 T[i] = (li, ri, xi) 형태입니다. 도로변에는 집을 지을 수 있는 자리가 총 n곳 있으며, 각 자리는 1부터 n까지 번호가 매겨져 있습니다. 집의 높이는 0부터 h 사이의 값으로 지을 수 있고, 어떤 자리에 높이 k인 집을 지으면 k2만큼의 수익을 얻게 됩니다.
여기에 m개의 구역 제한 조건이 붙습니다. i번째 제한은 “li번째 자리부터 ri번째 자리까지 구간에서 가장 높은 집의 높이는 xi를 넘을 수 없다”는 의미입니다. 목표는 이러한 제약 조건을 모두 만족하면서 수익을 최대화하는 것이며, 가능한 최대 이익을 구하는 프로그램을 작성해야 합니다.
예제로 이해하기
입력이 n = 3, h = 3, T = [[1,1,1],[2,2,3],[3,3,2]]라고 가정해 보겠습니다. 이 경우 출력은 14가 됩니다. 집은 총 3채를 지을 수 있고 최대 높이는 3입니다. 첫 번째 제한 조건에 따르면 1번 자리의 집 높이는 최대 1이어야 하고, 두 번째 제한에 따르면 2번 자리의 집 높이는 최대 3, 세 번째 제한에 따르면 3번 자리의 집 높이는 최대 2여야 합니다. 따라서 최적의 높이 배치는 [1, 3, 2]이며, 수익은 12 + 32 + 22 = 14가 됩니다.
풀이 접근 방법
이 문제는 탐욕적(greedy) 방식으로 해결할 수 있습니다. 먼저 모든 자리의 높이를 최대치인 h로 설정한 뒤, 각 제한 조건을 순회하면서 해당 구간에 포함된 자리들의 높이를 제한값 이하로 낮추면 됩니다. 각 자리는 결국 자신에게 적용되는 제한 중 가장 작은 값으로 결정되는데, 이것이 곧 해당 자리에서 지을 수 있는 최대 높이이므로 전체 수익 역시 자연스럽게 최대화됩니다.
알고리즘 단계
m := T의 크기
heights 배열을 크기 n으로 선언하고 모든 값을 h로 초기화
for i := 0 부터 i < m 까지 (i를 1씩 증가):
l := T[i][0]
r := T[i][1]
h := T[i][2]
for j := l - 1 부터 j < r 까지 (j를 1씩 증가):
heights[j] := heights[j]와 h 중 최솟값
ans := 0
for i := 0 부터 i < n 까지 (i를 1씩 증가):
ans := ans + heights[i] * heights[i]
ans 반환
C++ 구현 예제
아래 코드를 통해 풀이 과정을 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int h, vector<vector<int>> T){
int l, r;
int m = T.size();
vector<int> heights(n, h);
for (int i = 0; i < m; i++){
l = T[i][0];
r = T[i][1];
h = T[i][2];
for (int j = l - 1; j < r; j++)
heights[j] = min(heights[j], h);
}
int ans = 0;
for (int i = 0; i < n; i++)
ans += heights[i] * heights[i];
return ans;
}
int main(){
int n = 3;
int h = 3;
vector<vector<int>> T = { { 1, 1, 1 }, { 2, 2, 3 }, { 3, 3, 2 } };
cout << solve(n, h, T) << endl;
}
실행 결과
입력
n = 3, h = 3, T = { { 1, 1, 1 }, { 2, 2, 3 }, { 3, 3, 2 } }
출력
14
복잡도 분석
각 제한 조건마다 해당 구간을 한 번씩 순회하므로 시간 복잡도는 O(m × n)입니다. 공간 복잡도는 높이 정보를 저장하는 배열 때문에 O(n)입니다. 입력 크기가 크지 않다면 이 방식으로 충분히 빠르게 답을 구할 수 있습니다.