[SWEA] 8500. 극장 좌석

문제

좌석이 일렬로 나열된 극장에 N명의 사람이 앉아있다.

i번 사람의 왼쪽과 오른쪽으로 적어도 Ai개의 좌석이 연속해서 비어 있다.

즉, i번 사람은 2Ai개의 좌석이 비어 있는 것을 아는 것이다.

이 때, 극장의 좌석 개수로 가능한 수의 최소값을 구하는 프로그램을 작성하라.

사람들은 번호 순서대로 극장에 앉아 있는 것이 아님에 유의하라.

 

풀이방법

입력으로 2 3 2가 주어졌다는 말은 좌우에 빈좌석을 2개 필요로하는 사람, 3개 필요로하는 사람, 2개 필요로하는 사람이 있다는 의미.

 

문제에서 입력은 사람들이 앉은 순서대로 주어지지않았다는 점과 좌석의 최소한의 개수를 구하라고 했으므로

 

그리디 알고리즘으로 해결가능하다. 먼저 입력받은 수를 오름차순으로 정렬하고 앉은 사람의 사이마다 최소한의 좌석을 둔다.

 

필요한 좌석의 개수는 입력받은 사람의 수 + 각 사이마다 필요한 최소한의 좌석 수 + 맨 왼쪽의 빈 좌석 + 맨 오른 쪽의 빈 좌석이다.

 

소스코드

package samsung;

import java.util.*;

public class s_8500 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		
		for(int t = 1; t <= test; t++) {
			int n = sc.nextInt();
			int sum = 0;
			ArrayList <Integer> a = new ArrayList<>();
			for(int i = 0; i < n; i++) {
				int tmp = sc.nextInt();
				a.add(tmp);
			}
			Collections.sort(a);
			for(int i = 0; i < a.size(); i++) {
				sum += a.get(i);
			}
			sum += a.get(a.size() - 1);
			sum += n;
			System.out.println("#" + t + " " + sum);
			
		}
	}
}

 

출처

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

SW Expert Academy