park780172   6일 전

우선 저는 세그먼트 트리로 접근하려고 하였으나,

4 2

1 2 3 4

위와 같은 반례가 존재하였습니다.

위의 경우

(1) (2, 3, 4) → 1, 9 → 최솟값 : 1

(1, 2) (3, 4) → 3, 7 → 최솟값 : 3

(1, 2, 3) (4) → 6, 4 → 최솟값 : 4

☞ 1, 3, 4 중에 최댓값 : 4

즉, 답은 4이고,

단순한 세그먼트 트리로는 정답을 구할 수 없을 것 같은데,

어떻게 접근하면 좋을지 힌트 주실 분 계실까요..?

첨부한 코드의 경우

트리의 깊이에 따른 노드의 개수(1, 2, 4, 8, 16, ...)와 k를 활용하여(43 ~ 48 줄)

cnt를 구한 후에 tree[start] ~ tree[end - 1] 중 최솟값을 구하는 식으로 구현하였었습니다.(15 ~ 24 줄)

추가적으로 제 코드에

4 2

1 2 3 4

를 입력하면, 3이 나옵니다.

(tree[2](=3) ~ tree[3](=7) 중 최솟값은 3)

lovinix   6일 전

그룹마다 합의 최소를 미리 정하고 그에 끼워맞출 수 있는지 생각해보세요

park780172   3일 전

@lovinix 

감사합니다. 해결했습니다!

너무 복잡하게 생각했었던 것 같네요.

댓글을 작성하려면 로그인해야 합니다.