oVeron

1.금광을 개발했을 때의 가치는 2차원 배열로 나타낼 수 있다. 우리는 직사각형 형태의 구간을 정해 그 구간 내의 금광을 전부 개발했을 때의 가치의 최댓값을 구하고 싶다. 따라서 이 문제는 2차원 배열에서 부분합의 최댓값을 구하는 문제로 바꿔 풀 수 있다. 2.우선, 금광이 위치한 index의 범위가 매우 크므로 이를 값/좌표 압축으로 줄이자. \(N\)의 범위가 3000이므로 3000 이내의 2차원 배열로 모든 금광을 표현할 수 있다. 1차원 배열에서 부분합의 최댓값을 구하는 것은, 세그먼트 트리를 이용해 해결할 수 있음이 널리 알려져 있다.그렇다면 2차원 배열에서는 어떻게 하는가? x축을 기준으로 각 열의 누적 합을 구한 후 x축의 구간을 설정한다. 구간을 설정하기 위해서는 x축 내에서 2개의 값을 ..

알고리즘/baekjoon 2024. 7. 19. 12:27