알고리즘/BOJ

백준 10868번 최솟값

꾸준함. 2020. 3. 8. 20:16

문제 링크입니다: https://www.acmicpc.net/problem/10868

 

10868번: 최솟값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은

www.acmicpc.net

재채점 결과 틀렸습니다 처리가 되어서 다시 푼 문제였습니다.

세그먼트 트리만 구현하면 되는 문제였지만 최댓값이 1,000,000,000이기 때문에 종만북에서 무한대를 설정하듯이 987,654,321로 설정할 경우 오답처리가 되는 문제였습니다.

 

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1e5 + 1;
const int INF = 1e9 + 1;
long long arr[MAX];
long long segmentTree[4 * MAX];
long long initializeSegmentTree(int left, int right, int node)
{
if (left == right)
{
return segmentTree[node] = arr[left];
}
int mid = (left + right) / 2;
return segmentTree[node] = min(initializeSegmentTree(left, mid, node * 2), initializeSegmentTree(mid + 1, right, node * 2 + 1));
}
long long query(int left, int right, int node, int nodeLeft, int nodeRight)
{
if (nodeLeft > right || nodeRight < left)
{
return INF;
}
if (nodeLeft >= left && right >= nodeRight)
{
return segmentTree[node];
}
int mid = (nodeLeft + nodeRight) / 2;
return min(query(left, right, node * 2, nodeLeft, mid), query(left, right, node * 2 + 1, mid + 1, nodeRight));
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
for (int i = 1; i <= N; i++)
{
cin >> arr[i];
}
initializeSegmentTree(1, N, 1);
for (int i = 1; i <= M; i++)
{
int a, b;
cin >> a >> b;
cout << query(a, b, 1, 1, N) << "\n";
}
return 0;
}
view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

 

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

백준 11978번 Mowing the Field (Bronze)  (0) 2020.03.08
백준 3079번 입국심사  (0) 2020.03.08
백준 1043번 거짓말  (0) 2020.03.05
백준 11328번 Strfry  (0) 2020.03.02
백준 1267번 핸드폰 요금  (0) 2020.03.01