문제 링크입니다: 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로 설정할 경우 오답처리가 되는 문제였습니다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |


개발환경: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 |