값 n과 제한 조건 목록인 restrictions가 주어졌다고 가정해 보겠습니다. 우리는 도시에 n개의 새로운 건물을 세우려고 하지만, 몇 가지 제약 조건이 존재합니다. 건물들은 한 줄로 배치되며 1부터 n까지 번호가 붙습니다. 제한 조건은 두 개의 값을 가지는 쌍으로 표현되며, restrictions[i] = (id_i, max_height_i)는 id_i번 건물의 높이가 반드시 max_height_i 이하이어야 한다는 의미입니다.
새로 지어지는 건물들의 높이에 대한 도시 규정은 다음과 같습니다.
- 각 건물의 높이는 0 또는 양수여야 합니다.
- 첫 번째 건물의 높이는 반드시 0이어야 합니다.
- 인접한 두 건물 사이의 높이 차이는 1을 초과할 수 없습니다.
이러한 조건 안에서 우리는 가장 높은 건물이 가질 수 있는 최대 높이를 구해야 합니다.
예를 들어 입력이 n = 5, restrictions = [[2,1],[4,3]]라면 출력은 4가 됩니다. 가능한 최대 높이를 찾아야 하므로 아래 그림과 같이 최대 높이는 4가 될 수 있습니다.
문제 해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 만약 restrictions가 비어 있다면 n-1을 반환합니다.
- resi := restrictions를 id 기준으로 정렬한 리스트
- k := 0, idx := 1로 초기화
- resi의 각 요소 re에 대해 다음을 수행합니다.
- re[1] := min(re[1], k + re[0] - idx)
- k := re[1]
- idx := re[0]
- k := resi 마지막 요소의 높이 값
- idx := resi 마지막 요소의 id 값
- resi 리스트를 뒤집습니다.
- resi의 첫 번째 항목부터 각 요소 re에 대해 다음을 수행합니다.
- re[1] := min(re[1], k - re[0] + idx)
- k := re[1]
- idx := re[0]
- resi 리스트를 다시 원래 순서로 뒤집습니다.
- f := 0, idx := 1, res := 0으로 초기화
- resi의 각 요소 re에 대해 다음을 수행합니다.
- ff := min(f + re[0] - idx, re[1])
- res := max(res, (re[0] - idx + f + ff) // 2)
- idx := re[0]
- f := ff
- 최종적으로 max(f + n - idx, res)를 반환합니다.
예제 코드
더 나은 이해를 위해 다음 구현 예제를 살펴보겠습니다.
def solve(n, restrictions):
if not restrictions:
return n-1
resi = sorted(restrictions, key=lambda x: x[0])
k = 0
idx = 1
for re in resi:
re[1] = min(re[1], k + re[0] - idx)
k = re[1]
idx = re[0]
k = resi[-1][1]
idx = resi[-1][0]
resi.reverse()
for re in resi[1:]:
re[1] = min(re[1], k - re[0] + idx)
k = re[1]
idx = re[0]
resi.reverse()
f = 0
idx = 1
res = 0
for re in resi:
ff = min(f + re[0] - idx, re[1])
res = max(res, (re[0] - idx + f + ff) // 2)
idx = re[0]
f = ff
return max(f + n - idx, res)
n = 5
restrictions = [[2,1],[4,3]]
print(solve(n, restrictions))
입력
5, [[2,1],[4,3]]
출력
4