[백준 / C#] 10868. 최솟값 (G1)

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

10868번: 최솟값

 

세그먼트 트리를 사용해 고난이도 문제를 날로 먹어보자 시리즈(1)

 

구간별 최솟값 세그먼트 트리를 만들어서 풀면 되는 문제이다. 세그먼트 트리를 만들면 리프 노드는 각각의 입력값이 되고 리프 노드 중 더 작은 값이 리프노드의 상위 노드가 된다. 그렇게 올라가다 보면 루트 노드는 자연스럽게 전체 구간의 최솟값이 된다. 세그먼트 트리를 만들었다면 주어진 구간만 잘 고려하면 해결할 수 있다.

 

도구는 검증됐으니 될때까지 박으면 된다!

 

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;

namespace ConsolApplicaton3
{
    class Program
    {
        static long[] arr;
        static long[] tree;
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            String[] input = Console.ReadLine().Split();
            int n = int.Parse(input[0]);
            int m = int.Parse(input[1]);
            int a, b;
            arr = new long[n];
            tree = new long[arr.Length * 4];
            //tree = new List<int>();
            for (int i = 0; i < n; i++)
                arr[i] = int.Parse(Console.ReadLine());
            init_min(0, arr.Length - 1, 1);
            while (m > 0)
            {
                m--;
                String[] tmp = Console.ReadLine().Split();
                a = int.Parse(tmp[0]);
                b = int.Parse(tmp[1]);
                sb.Append(min(0, arr.Length - 1, 1, a - 1, b - 1) + "\n");
            }
            Console.WriteLine(sb);
        }
        static long init_min(int start, int end, int index)
        {
            if (start == end)
            {
                tree[index] = arr[start];
                return tree[index];
            }
            int mid = (start + end) / 2;
            tree[index] = Math.Min(init_min(start, mid, index * 2), init_min(mid + 1, end, index * 2 + 1));
            return tree[index];
        }
        static long min(int start, int end, int index, int left, int right)
        {
            if (left > end || right < start)
                return (int)1e9 + 1;
            if (left <= start && right >= end)
                return tree[index];
            int mid = (start + end) / 2;
            return Math.Min(min(start, mid, index * 2, left, right), min(mid + 1, end, index * 2 + 1, left, right));
        }
    }
}