8500

using namespace std;

static int N;
static int AN[10000];

static int solution(void)
{
	int ret = 0, max = 0;

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &AN[i]);
		if (AN[i] > max)
			max = AN[i];
		ret += AN[i];
	}
	ret += (N + max);
	
	return ret;
}

코드는 간단한데, 생각하는 방법이 중요했던 것 같다.

초기에 생각했던 컨셉은 다음과 같다.

 

먼저 AN배열을 오름차순으로 정렬한다.

그리고 그 순서대로 배치를 해본다.

그래서 [5][4][3][2][1]로 되어 있으면,

 

*****[5]*****[4]****[3]***[2]**[1]*, (*은 공석이고, [x]는 x가 앉은 위치를 의미한다.)

위와 같이 배치 할 수 있다.

양 옆으로 공석이 큰 숫자를 먼저 배치 시켜야, 이보다 작거나 같은 수 에 대해서는 왼편의 오는 공석을 따로 추가하지 않아도 되기 때문이다. 

즉, 큰 수에서 필요한 공석으로 작은 수에서 필요한 공석을 흡수해버리는 것이다.

 

그래서 좌석의 개수는

5 + (5 + 4 + 3+ 2 + 1) + (N == 5) 가 된다.

식을 세우고 보면, 입력을 차례대로 더한 뒤, N 값을 더해주고, 입력의 최대 값을 더해주면 되는 구조임을 알 수 있다.

 

그래서 입력을 받은 후 정렬 없이, 위 코드처럼 구하면 되는 것이다.

 

//

보통 최소값을 구하라는 문제에서는

전수 조사를 하면서 최소값을 업데이트 하는 방식으로 구하는 것이 생각보다 많았지만,

이 문제에 경우는 그러지 않았다.

더욱이, N이 최대 1만 까지 주어지기에 애초에 그렇게 시도해보려 하지도 않았다.