목록segment tree (1)

dh_0e

[PS] 수열과 쿼리 16 / C++ (백준 14428번)

수열과 쿼리 16 (백준 14428번) 읽자마자 세그먼트 트리가 떠올랐던 문제. 값이 아닌 인덱스를 출력하는 문제이기 때문에 세그먼트 트리를 적절히 변형하여 풀어야 한다. 풀이 과정 값과 인덱스 모두 저장해야 하기 때문에 tree[] 배열을 pair로 선언해주고, 모든 함수 또한 return 값을 pair로 하여 세그먼트 트리를 구현해주면 된다. pair init(int start, int end, int node): 세그먼트 트리를 만드는 함수로 기존 세그먼트 트리 로직에 최솟값과 그 인덱스를 pair로 가져오게끔 수정하면 된다. 이때, 최솟값이 같을 경우 인덱스가 작은 것을 출력하기 때문에 조건문은 if(left_node.firstright_node.first)tree[node]=left; 가 된다..
Problem Solving/Baekjoon 2025. 7. 29. 11:09
이전 Prev 1 Next 다음