[ SWEA 7730 ] 나무 깎는 홍준 (C++)

SWExpertAcademy의 나무깎는 홍준(7730 / D5) 문제이다.

[ 문제풀이 ]

원목 M만큼을 얻기 위해, 절단해야 하는 높이 중 최대 높이를 구해야 하는 문제이다.

주어질 수 있는 높이의 최대값이 10^9 이기 때문에, 모든 값에 대해서 하나하나 완전탐색을 진행한다면, 주어진 시간제한 내에 통과하지 못할 것 같아서 본인은 이분탐색을 이용해서 문제에 접근하였다.

가장 초기 Left의 값은 0으로, Right의 값은 트리의 높이 중 가장 높은 값으로 설정을 해 주었다.

그리고 이분탐색을 이용해서 탐색을 진행해 주었다.

주어진 , Left Right값을 통해서 Mid값을 구한 후 , 해당 Mid값으로 나무들을 잘랐을 때, 얻을 수 있는 원목이 M보다 크다면, 값을 더 크게 만들어서 탐색을 진행해 주었고, 아니라면 값을 조금 낮춰서 진행해주는 이분탐색을 반복해 주었다.

그리고 ! 탐색을 할 때에 구한 원목의 양이 int형의 범위를 초과할 수 있으니, long long으로 설정해 주어야 한다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 1000010
using namespace std;
 
int N, M;
int Tree[MAX];
long long Answer;
 
void Initialize()
{
 
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> Tree[i];
}
 
bool Binary_Search(int Mid)
{
    long long Result = 0;
    for (int i = 0; i < N; i++)
    {
        if (Tree[i] > Mid) Result = Result + (Tree[i] - Mid);
    }
    if (Result >= M) return true;
    return false;
}
 
void Solution()
{
    int Left = 0;
    int Right = 0;
    for (int i = 0; i < N; i++)
    {
        if (Tree[i] > Right) Right = Tree[i];
    }
    
    while (Left <= Right)
    {
        int Mid = (Left + Right) / 2;
        if (Binary_Search(Mid) == true)
        {
            Answer = Mid;
            Left = Mid + 1;
        }
        else Right = Mid - 1;
    }    
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}