[SWEA] 8500. 극장 좌석 문제풀이 _ Java

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWz5yIfq74QDFARQ

SW Expert Academy

 

 

풀이

문제의 힌트는 "사람들은 번호 순서대로 극장에 앉아 있는 것이 아님에 유의하라." 이 문장에서 찾아볼 수 있었습니다.

가능한 최소의 극장 좌석의 수를 만들면 되는 문제이므로, 

2번째 테스트 케이스처럼 5, 2, 3, 1, 4 가 input으로 들어온다면 1, 2, 3, 4, 5로 배치하고 최소값을 찾을 수 있습니다.

좌석간의 간격의 수로 정렬을 한 뒤에 생각해보면

항상 가장 큰 수만 2번 ( max값은 항상 양옆으로 모두 비워야 하기 때문에 ) 더하면 결과값을 찾을 수 있습니다. 

따라서 정답 출력을 ( sum + max + N )으로 모든 간격의 합(sum)과 max값, 사람이 앉을 N명의 값을 더해

출력해주면 되는 문제였습니다.

 

 

코드