백준 10868번 최솟값[C/C++]

1. 문제 풀이

 이번에 풀어본 문제는 10868번 최솟값입니다. 문제의 유형은 세그먼트 트리입니다. 세그먼트 트리의 구간 합을 구하는 쿼리 연산을 구간의 최솟값을 찾는 연산으로 응용하여 사용할 수 있습니다. 트리를 구성할 때도 최솟값을 가지도록 구현해야 합니다.

 

2. C++ 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int inf = 1e9;

int n, m;
int tree[200'005];

int query(int l, int r){
  int ret = inf; 
  for(l += n, r += n; l < r; l>>=1, r>>=1){
    if(l&1) ret = min(ret, tree[l++]);
    if(r&1) ret = min(ret, tree[--r]);
  }
  return ret;
}

int main() {
  fastio(nullptr, false);
  cin >> n >> m;
  for(int i = 0; i < n; i++) cin >> tree[i+n];
  for(int i = n-1; i > 0; --i) tree[i] = min(tree[i<<1], tree[i<<1|1]);
  
  while(m--){
    int a, b;
    cin >> a >> b;
    cout << query(a-1, b) << nl;
  }
}

 

3. C 코드

#include <stdio.h>
#define inf 1000000005

int n, m;
int tree[200005];

int min(int a, int b){ return (a < b) ? a : b; }

int rmq(int l, int r){
  int ret = inf;
  for( l += n, r += n; l < r; l>>=1, r>>=1){
    if(l&1) ret = min(ret, tree[l++]);
    if(r&1) ret = min(ret, tree[--r]);
  }
  return ret;
}

int main(){
  scanf("%d %d ", &n, &m);
  for(int i = 0; i < n; i++) scanf("%d ", &tree[i+n]);
  for(int i = n-1; i > 0; i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);

  while(m--){
    int a, b;
    scanf("%d %d ", &a, &b);
    printf("%d\n", rmq(a-1, b));
  } 
}

4. 제출 결과