[SW Expert Academy] - (D3)8500. 극장 좌석

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

SW Expert Academy

코드

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int T = scan.nextInt();
		for(int tc=1; tc<=T; tc++) {
			int N = scan.nextInt();
			int[] seats = new int[N];
			for(int i=0; i<seats.length; i++) {
				seats[i] = scan.nextInt();
			}
			Arrays.sort(seats);
			
			int minSeats = N;	// N명의 좌석이 필요하므로 초기값으로 N 설정
			
			for(int i=0; i<seats.length; i++) {
				minSeats += seats[i];
			}
			
			minSeats += seats[seats.length-1];	// 가장 오른쪽 사람의 자리 더하기
			
			System.out.println("#" + tc + " " + minSeats);
			
		}
		
		scan.close();
	}

}

풀이

극장의 좌석 개수를 최소한이 되게하려면 어떻게 자리를 설정해야 최소값이 나올지 생각해보면 된다.

주어진 테스트케이스 2번의 경우 5 2 3 1 4 이다.

 

o o o o o 5 o o o o o 2 o o 3 o o o 1 o o o o 4 o o o o

 

주어진 대로라면 최소한의 좌석개수는 위와 같이 28개의 좌석이 필요하다.

 

최소한이 되게 하려면 숫자가 비슷한 값들끼리 인접한 자리로 설정하면 된다.

즉 정렬을 하면 된다.

 

o 1 o o 2 o o o 3 o o o o 4 o o o o o 5 o o o o o

 

위와 같이 설정하면 좌석 개수는 최소가되고, 25개의 좌석이 필요하다.

 

그럼 위와 같이 됐을때, 좌석의 개수는 해당 값을 더하고, N명과 가장 큰 값(마지막값) 을 더해주면 된다.