[백준 - C#] 9237번 이장님 초대

문제링크

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

9237번: 이장님 초대

 

문제

농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다.
묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다.
상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.
상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 이장님을 며칠에 초대할 수 있을까?

조건

시간제한 : 1초
메모리 제한 : 128 MB

입력

입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000)

출력

첫째 줄에 며칠에 이장님을 초대할 수 있는지 출력한다.
답이 여러 가지인 경우에는 가장 작은 값을 출력한다. 묘목을 구입한 날이 1일이다.

 

문제정리

1. 묘목 하나를 심는데 걸리는 시간은 1일
2. 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다
3. 마지막 나무가 다 자란 다음날 이장님을 초대

이번 문제는 상근이가 묘목을 다 심고 자라게 했을 때 이장님을 초대하는 것인데 묘목을 얼마나 빨리 다 자라게 하는 것이 관건인 문제입니다.

묘목은 하루에 하나씩 심을 수 있고 자라는데 가장 오래걸리는 묘목을 먼저 심는게 가장 짧은 시간이라고 판단이되어 묘목이 자라나는 시간에 대해서 내림차순으로 정렬 후 최종적으로 나무가 자라는 시간을 구했습니다.

 

첫 묘목 : 현재 날짜 1일 + 묘목 자라는 시간

두번째 묘목 : 현재 날짜 2일 +  묘목 자라는 시간

세번 째 묘목 : 현재 날짜 3일 + 묘목 자라는 시간

=> (i + 1) + 묘목 자라는 시간입니다.

 

그렇게 모든 묘목에 대해서 자라는 시간이 정의가 된다면 그중 max 값이 정답 인데 묘목이 자라는 시간은 2일 째였었기 때문에 +1(첫날)을 해주었습니다.

 

C# 코드

static void Main(string[] args)
{
    // 9237 이장님 초대
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    int N = int.Parse(reader.ReadLine());
    int[] tree = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
    int[] day = new int[N];
 
    // 내림 차순 정렬
    Array.Sort(tree);
    Array.Reverse(tree);
 
    for (int i = 0; i < N; i++)
        day[i] = i + 1 + tree[i]; // 나무가 자라는데 걸리는 시간
 
    writer.WriteLine(day.Max() + 1); // 최고로 오래걸리는 나무시간 + 첫날 심는 시간
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.