[백준 21599] 아이템 배치하기 (C++)

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

 

문제

---

최근 싸이컴에서 제작한 게임 ‘입부 전쟁’에서는 다양한 아이템을 활용해 전쟁의 승리 확률을 높일 수 있습니다. 아이템은 한 번에 𝑁개씩 강화할 수 있습니다.

강화력이 각각 𝐴₁,𝐴₂,⋯,𝐴_𝑁개의 아이템을 강화하려고 할 때, 아이템을 강화하는 방법은 다음과 같습니다.

•  𝑁$개의 아이템을 적절한 순서로 원형으로 배열합니다.
•  𝑖$번 아이템은 자신부터 시작해, 시계 방향으로 𝐴_𝑖개의 아이템을 강화시킵니다. 𝐴_𝑖=0인 아이템의 경우 다른 아이템에게 아무 영향도 주지 않습니다.
• 만약 위 규칙에 의해 여러 번 강화되는 아이템이 있다면, 실제로는 한 번만 강화됩니다.

브루는 ‘입부 전쟁’ 세계 1위를 기록한 흑왕을 이기기 위해 아이템을 강화하려고 합니다. 하지만 브루는 어떤 식으로 배치해야 최대한 많은 아이템을 강화할 수 있을지 찾지 못했고, 당신에게 도움을 요청했습니다. 그러나 당신도 ‘입부 전쟁’ 게임을 열정적으로 하는 플레이어이기 때문에, 브루의 아이템 강화를 방해하려고 합니다. 따라서 당신은 브루의 부탁대로 가장 많은 아이템을 강화하게 하는 대신, 가장 적은 아이템을 강화시키는 방법을 찾으려고 합니다.

 𝑁개의 아이템과 각각의 강화력 𝐴₁, 𝐴₂, ⋯, 𝐴_𝑁이 주어졌을 때, 최대한 적은 아이템만 강화되게 하고, 그때 강화되는 아이템의 수를 구해 출력하세요.

 

입력

---

첫 줄에는 아이템의 수를 나타내는 정수 𝑁이 주어집니다.

둘째 줄에는 각 아이템의 강화력을 나타내는 정수 𝐴₁, 𝐴₂, ⋯, 𝐴_𝑁이 주어집니다.

 

출력

---

가능한 모든 아이템 배치들 중에서, 강화되는 아이템 수의 최솟값을 출력합니다.

 

문제 풀이

---

정렬+그리디 문제.

강화되는 아이템 수를 최소화하려면 강화되는 아이템을 최대한 겹치게 배치해야 한다. 따라서 내림차순으로 정렬해주면 최솟값을 얻을 수 있다. 

강화되는 아이템의 개수를 세면 되는데 입력을 저장한 배열을 arr라 했을 때, i번째 아이템을 강화하면 i+arr[i] - 1(단, arr[i] !=0 )번 인덱스 아이템까지 강화된다. 내림차순 정렬이므로 순차적으로 탐색하면 중간에 강화하지 못하는 아이템이 없다. 따라서 강화하는 아이템 수는 i+arr[i]로 얻어질 수 있는 최대 개수가 된다. 또한 정답은 N을 넘지 못하므로 넘을 수 없도록 min(answer, N)을 통해 정답을 조절한다.

 

예시로, 정렬했을 때 배열의 값이 4 4 2 0 0이라 가정해보자.

0번째 인덱스 아이템을 강화하면 index 3 아이템까지 4개 아이템이 강화된다. 여태까지 인덱스 0 아이템에 의해 4개 아이템이 강화되었다.

 

1번째 인덱스 아이템을 강화하면 index 4 아이템까지 4개 아이템이 강화된다. 여태까지 인덱스 1 아이템에 의해 5개 아이템이 강화되었다.

 

2번째 인덱스 아이템을 강화하면 index 3 아이템까지 2개 아이템이 강화된다. 여태까지 인덱스 1 아이템에 의해 5개 아이템이 강화되었다.

 

따라서 위의 답은 5가 된다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	int* arr = new int[N];
	int answer = 0;
	int index = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N, greater<int>());
	for (int i=0;i<N;i++)
	{
		if (arr[i] == 0)
		{
			break;
		}
		answer = max(answer, i + arr[i]);
	}
	cout << min(answer, N) << "\n";
	return 0;
}