[BOJ/백준 9237][C++] 이장님 초대

문제

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

 

문제 내용

묘목 하나를 심는데 1일이고, 묘목이 자라는 데 걸리는 시간은 주어진다.

묘목이 다 자라면 그다음 날에 이장님을 초대하려고 한다.

이때 이장님을 며칠 만에 초대할 수 있을지를 구하면 된다.

 

문제 풀이

크게 생각할것도 없이 무조건 자라는데 오래 걸리는 묘목부터 심어야 한다. (greedy 문제이다)

그래야 자라는 동안 새 묘목을 심어 최대한 기간이 겹치게 할 수 있다.

이를 위해서 sort()로 정렬해주었다.

이때, 내림차순으로 정렬하기 위해서 sort()의 세 번째 인자에 비교 함수 compare를 만들어 넣어 주었다.

 

내림차순으로 정렬이 완료되면, 이제 기간을 체크해야 한다.

문제에 주어진 예제 입력 1을 살펴보겠다.

아래의 사진은 묘목을 심고, 이장님을 초대하는 날을 제외하고 그린 기간이다. 

[2,3,4,3]을 내림차순으로 정렬하면 [4,3,3,2]가 된다.

그렇다면 위와 같이 5일 동안 묘목이 자라는 것을 알 수 있다.

5일이라는 기간을 코드로 어떻게 구현할까 고민을 했다.

 

내가 선택한 방법은 앞부분을 채워나가는 방식이다.

그렇다면 가장 0번 묘목은 자신의 원래 기간 그대로 적용된다.

1번 묘목은 1+(1번의 생장 기간), 2번 묘목은 2+(2번의 생장 기간),.... 이런 식으로 진행될 것이다.

즉, i번 묘목이 다 자라면 i+(i번의 생장 기간) 만큼의 기간이 지나게 된다.

 

이후, 새로 저장한 묘목의 생장 기간 중에서 가장 큰 값을 찾으면 된다.

출력 시에는 나무를 심고, 이장님을 부르는 날이 있기 때문에 +2 해서 출력해주면 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool compare(const int& a, const int& b) {
	if (a > b) return true;
	else return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n;
	cin >> n;
	vector<int>time(n);
	for (int i = 0; i < n; i++) cin >> time[i];

	//문제 해결
	sort(time.begin(), time.end(), compare);

	for (int i = 0; i < n; i++) {
		time[i] += i; //앞부분 빈칸 채워가기
	}

	int mmax = time[0];
	for (int i = 1; i < n; i++) {
		mmax = max(mmax, time[i]);
	}

	//+2 하는 이유: 첫날 심는 것 + 이장님 초대 
	cout <<  mmax+2 << '\n'; 
}