SW Expert Academy 8500. 극장 좌석

문제링크 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWz5yIfq74QDFARQ&categoryId=AWz5yIfq74QDFARQ&categoryType=CODE

SW Expert Academy

#include <iostream>
using namespace std;

int main()
{
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++)
	{
		int N = 0, max = 0;
		int result = 0;
		cin >> N;
		int* arr = new int[N];
		for (int i = 0; i < N; i++)
		{
			cin >> arr[i];
			if (max < arr[i])
			{
				max = arr[i];
			}
			result += arr[i] + 1;
		}
		result += max;
		cout << "#" << t << ' ' << result << '\n';
		delete[] arr;

	}

}

 

극장 자리의 최소 자리의 개수를 찾는 문제이다.

 

2번이 들어왔을 때는 최소 5개의 자리가 필요하고

3번은 최소 7개의 자리가 필요하지만, 이들이 나란히 앉을 때 중복되는 자리를 빼야 최소의 자리수가 나온다

예를 들면 0 을 빈 자리라고 하고

2번과 3번이 들어왔을 때,

 

0 0 2 0 0

        0 0 0 3 0 0 0

 

위와 같은 구조를 띄게 되며 일렬로 나열하면 아래와 같다.

0 0 2 0 0 0 3 0 0 0

 

이랬을 때, (0 0 2 + 0 0 0 3)을 하고 나면 남는 빈자리는 3개인데, 이 수는 N번 에서 N과 같기에

각 입력 숫자를 더하고 최대값으로 들어온 숫자를 넣으면 최소자리 계산이 된다.