[백준 BOJ] 9237번 이장님 초대 (C++/cpp)

문제 설명

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

9237번: 이장님 초대

 

접근 방법 - 정렬을 활용한 그리디 알고리즘 문제

백준의 9237번 문제는 정렬을 이용하여 해결해야 하는 그리디 알고리즘 문제이다.

해당 문제는, 하나의 나무를 심는 데에 하루가 걸린다고 가정하였을 때 나무가 모두 자라고 이장님을 가장 빨리 초대할 수 있는 날이 언제인지를 출력해야 하는 문제이다.

이때 나무들이 모두 자라는 데에 최소 소요 일수를 구해야 하기 때문에, 자라는 데에 가장 오래 걸리는 나무를 가장 먼저 심는 식으로 연산을 진행해야 할 것이다.

또한 하나의 나무를 심는 데에 하루가 소요되기 때문에, 위 방법으로 모든 나무를 심고 난 이후 가장 늦게 자라는 나무를 기점으로 정답을 구해보았다.

자세한 설명은 아래에서 계속 진행되니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 나무의 개수(n)를 입력받고, 나무가 자라는 일수를 각각 저장할 배열(namu)을 선언한다.

 

2) n의 크기만큼, 배열 namu의 값들을 하나씩 입력받는다.

 

3) sort() 함수를 이용하여, namu의 값들을 내림차순 정렬한다.

이때, compare 함수를 아래 코드처럼 임의로 작성하고 적용하여 내림차순으로 정렬하게끔 설정한다.

bool compare(int a, int b) {
	return a > b;
}

 

4) 나무들을 모두 다 심은 뒤, 모두 온전히 자라는 데에 걸리는 일수를 저장할 변수(max)를 0으로 초기화하며 선언한다.

 

5) 제어 변수 i를 0부터 n-1까지 순회시키며, 아래의 연산을 수행한다.

- 기존에 저장된 namu[i]의 값에 (n-(i+1))의 값을 뺀다.

이 연산을 수행하고 나면, namu[i]에는 모든 나무들을 심고 난 뒤 해당 나무가 온전히 자라는 데에 필요한 시간이 저장된다.

- 만일 현재 namu[i]의 값이 max보다 크다면, max에 현재 namu[i] 값을 저장한다.

 

6) 정답을 저장할 변수 result를 선언한 뒤, n+max+1 값을 저장하도록 한다.

- n 추가 :: 모든 나무를 심는 데에 걸리는 소요 일수

- max 추가 :: 모든 나무를 심고 난 뒤에, 모든 나무가 온전히 자라는 데에 필요한 소요 일수

- 1 추가 :: 모든 나무가 자란 뒤, 이장님을 그다음 날에 초대하기 때문에 필요한 연산

 

7) result의 값을 출력한 뒤, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 9237번 코드
bool compare(int a, int b) {
	return a > b;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);   cout.tie(NULL);

	int n;
	cin >> n;
	int namu[100001];
	for (int i = 0; i < n; i++) {
		cin >> namu[i];
	}
	sort(namu, namu + n, compare);

	int max = 0;
	for (int i = 0; i < n; i++) {
		namu[i] -= (n - (i + 1));
		if (namu[i] > max) { max = namu[i]; }
	}

	int result = n + max + 1;
	cout << result << endl;
}

 

제출 결과

(2023.08.20 백준 9237번 문제 제출 결과)