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

1. 문제이해

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

9237번: 이장님 초대

 

상근이는 묘목을 심어 나무가 다 자랐을 때 이장님을 초대하려고 한다. (묘목 하나를 심는데는 1일이 걸린다.)

묘목의 수(N)와 각 묘목이 자라는데 걸리는 시간(t)을 입력받아,

이장님을 가장 빨리 초대할 수 있는 경우에 걸리는 시간을 계산하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

묘목 하나를 심는데 하루가 걸리니, 기본적으로 N개의 묘목을 심을때, 나무를 심는데 걸리는 시간은 N일이다.

또한, 첫번째 나무를 심고 난 뒤에는 하루가 걸리니, 2일이 된다. 

예를 들어, 다 자라는데 5일이 걸리는 나무를 심는다고 생각해보자.

묘목을 심는데만 하루가 걸리기 때문에 2일째부터 5일이 걸린, 7일째에 나무가 다 자라게 된다.

즉, 2일째 부터 묘목이 자라는데 걸리는 시간을 더해주어야 한다는 뜻이다.

 

그렇다면, 이장님을 가장 빠른 시일 내에 초대하려면 어떻게 해야 할까?

오래걸리는 나무를 먼저 심어야할까? 금방자라는 나무를 먼저 심어야 할까?

당연히 전자이다.

예를 들어 다 자라는데 2일, 9일이 걸리는 나무묘목 2개를 심는다고 하자.

오래걸리는 나무를 먼저 심으면,

2일째부터 9일이 걸리기 때문에 다 자라면 11일,

그 다음날인 3일째에 2일 걸리는 나무를 심으면 5일째에 다 자라게 된다.

따라서, 11일이면 이장님을 초대할 수 있다.

 

반면, 금방 자라는 나무를 먼저 심게 되면,

2일째에 2일걸리는 나무를 심어 다 자라면 4일,

3일째에 9일 걸리는 나무를 심어 12일째에 다 자라게된다.

 

이렇듯, 전자의 경우보다 하루가 더 걸리는 12일째에 이장님을 초대할 수 있게 된다.

오래걸리는 나무를 빨리 심어야 그만큼 시간을 단축할 수 있게 된다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>

using namespace std;
int tree[1000000];
int treemin[1000000];

// 내림차순
bool DESC(int a, int b) {
	return a > b;
}

int main() {

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> tree[i];	// 나무가 자라는데 걸리는 시간
	}
	
	// 내림차순으로 정렬
	sort(tree, tree + N, DESC);

	// 현재의 날짜 + 나무가 자라는데 걸리는 시간
	for (int i = 0; i < N; i++) {
		treemin[i] = (i + 1) + tree[i];
	}

	// 총 걸리는 시간을 내림차순으로 정렬 (제일 첫번째값이 총 걸리는 시간)
	sort(treemin, treemin + N, DESC);

	// 묘목을 심고나면 2일째부터 시작하므로 (i+1)
	cout << treemin[0] + 1;

	return 0;
}

묘목의 갯수(N)를 입력받고, 각 나무가 자라는데 걸리는 시간(tree)을 입력받아 배열에 저장한다.

오래걸리는 나무를 먼저 심어야하므로, tree를 내림차순으로 정리하고,

이를 현재의 날짜(ex)1일째, 2일쨰...)에 더해준다. (treemin)

이중에서 가장 큰 값이 모든 묘목이 다 자라는데 걸리는 시간으므로,

treemin을 다시 내림차순으로 정렬해준다.

정렬했을때, 맨 첫번째 값이 제일 큰 값이 되므로,

treemin[0] 값에 1을 더해주어 출력한다. (2일째 부터 시작이므로)

 

 

---

이 문제도 계속 이해가 안가서 몇번을 다시 본것같다.

특히, 나무 하나를 심는데 하루가 걸리므로 2일째부터 묘목이 자라는 것을 계산해주는것.

이것때문에 한참을 고민했다..

분명히 예제 값을 보면 1씩 작아져서 나오는데.. 하고..😂

개인적인 생각인데, 이런 코딩 문제들을 보면서 요즘 드는 생각이,

어렸을 때 하던 닌텐도의 레이튼 교수와 이상한 마을이라는 게임의 문제들과 비슷하다는 느낌이 든다..ㅎㅎ 나만그런가