세그먼트 트리 :: 백준 :: 최소값과 최대값 :: 2357

최대값과 최소값

https://www.acmicpc.net/problem/2357

세그먼트트리를 활용하여 푸는 문제이다.

세그먼트트리를 모른다면 구글을 활용해 검색해보자. 자세한 설명들이 많이 올라와있다.

[문제 풀이]

먼저, 2열부터 11열까지 숫자를 입력받아 tree 배열에 집어넣는다. 인덱스를 신경써야 한다.

idx	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
																75	30	100	38	50	51	52	20	81	5	X	X	X	X	X	X

세그먼트 트리를 완성시키면 다음과 같은 모습이 된다.(문제는 최솟값, 최댓값을 구하라고 했지만, 편의상 지금은 최솟값만 구했다.)

idx	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
	5	20	5	30	20	5	X	30	38	50	20	5	X	X	X	75	30	100	38	50	51	52	20	81	5	X	X	X	X	X	X

이 상태에서 주어진 범위에 해당하는 최솟값을 찾는다.

예를 들어 두 번째 케이스인 3, 5의 경우

query(1, 16, 31, 18, 20)         L : 38    R : -1

L : query(2, 16, 23, 18, 20)            L : 38    R : 50

L : query(4, 16, 19, 18, 20)            L : -1    R : 38

L : query(8, 16, 17, 18, 20)

R : query(9, 18, 19, 18, 20)

R : query(5, 20, 23, 18, 20)            L : 50    R : -1

L : query(10, 20, 21, 18, 20)            L : 50    R : -1

L : query(20, 20, 20, 18, 20)

R : query(21, 21, 21, 18, 20)

R : query(11, 22, 23, 18, 20)

R : query(3, 24, 31, 18, 20)

위와 같은 과정으 거쳐 최솟값으로 38을 구할 수 있다.

최댓값 같은 경우는 살짝만 조작하면 바로 구할 수 있음!

사실 10868번 문제가 조금 더 기본문제라고 생각한다. 10868번 문제를 먼저 풀어보는 것이 이 문제를 푸는데 도움이 될 것이라 생각함.