[정올][다이나믹] 1848 극장좌석

극장좌석문제는 다이나믹 프로그래밍으로 풀이가 가능하다. 

전제조건은 좌우 한칸으로는 이동이 가능하다.

좌석이 2개일 경우 아래의 두개의 경우가 가능

• 1, 2
• 2, 1

좌석이 3개일때는 좌석이 2개인 경우에서 끝자리가 2인 경우는 3과 교환이 가능하기 때문에 2가지 경우가 나오고, 1인경우는 3과 교환이 불가능 하여 끝에 3이 붙는  하나의 경우만 나온다. 

끝이 2 인 경우: (1*2)/2 + 1 = 2

끝이 2 이 아닌 경우: (1*2)/2 = 1

좌석이 3개인 경우 3가지 종류가 가능

• 1, 2 -> 1, 2, 3  
•            1, 3, 2
• 2, 1 -> 2, 1, 3

좌석이 4개일때는 좌석이 3개인 경우에서 끝자리가 3인 경우는 4와 교환이 가능하기 때문에 4가지 경우가 나오고, 2인 경우는 4와 교환이 불가능하이 끝에 4가 붙는 하나의 경우만 나온다. 

• 1, 2, 3 -> 1, 2, 3, 4
•                1, 2, 4, 3
• 2, 1, 3 -> 2, 1, 3, 4
•                2, 1, 4, 3
• 1, 3, 2 -> 1, 3, 2, 4

끝이 3인 경우: (2*2)/2 + 1 = 3

끝이 3이 아닌 경우: (2*2)/2 = 2

좌석이 4개인 경우 5가지 종류가 가능

즉 앞좌석의 마지막 좌석번호를 이용하여 다음 좌석의 개수를 계산이 가능하다. 

	package sdk.algo.dynamic;
	import java.util.Scanner;
	/**
	* 정올, 다이나믹 프로그래맹, 1848
	*
	* @author whitebeard-k
	*
	*/
	public class Problem1848 {
	// 메모이제이션을 위한 배열
	public static int[][] memo = new int[50][2];
	public static void main(String[] args) {
	// int N = 40;
	// int staticSeatNum = 2;
	// int[] staticSeats = { 4, 7 };
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int staticSeatNum = sc.nextInt();
	int[] staticSeats = new int[staticSeatNum];
	for (int i = 0; i < staticSeatNum; i++) {
	staticSeats[i] = sc.nextInt();
	}
	sc.close();
	if (staticSeatNum == 0) { // 고정 좌석의 개수가 0개
	System.out.println(calc(N));
	} else if (staticSeatNum == 1) { // 고정 좌석의 개수가 1개
	int first = (staticSeats[0] - 1 <= 1) ? 1 : calc(staticSeats[0] - 1);
	int end = (staticSeats[staticSeatNum - 1] + 1 >= N) ? 1 : calc(N - staticSeats[staticSeatNum - 1]);
	System.out.println(first * end);
	} else { // 고정 좌석이 2개 이상
	int first = (staticSeats[0] - 1 <= 1) ? 1 : calc(staticSeats[0] - 1);
	int end = (staticSeats[staticSeatNum - 1] + 1 >= N) ? 1 : calc(N - staticSeats[staticSeatNum - 1]);
	int result = 1;
	int prev = staticSeats[staticSeatNum - 1];
	for (int i = staticSeatNum - 2; i >= 0; i--) {
	result *= calc(prev - staticSeats[i] - 1);
	prev = staticSeats[i];
	}
	System.out.println(first * result * end);
	}
	}
	public static int calc(int n) {
	if (n == 0)
	return 1;
	if (n == 1) {
	memo[n][0] = 1; // 현재 번호로 끝나는 좌석 개수
	memo[n][1] = 0; // 현재 번호로 끝나지 않는 좌석 개수
	} else if (n == 2) {
	memo[n][0] = 1;
	memo[n][1] = 1;
	} else if (memo[n][0] == 0) {
	if (memo[n - 1][0] == 0) {
	calc(n - 1);
	}
	memo[n][0] = (memo[n - 1][0] * 2) / 2 + memo[n - 1][1];
	memo[n][1] = (memo[n - 1][0] * 2) / 2;
	}
	return memo[n][0] + memo[n][1];
	}
	}

view raw Problem1848.java hosted with ❤ by GitHub

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1121&sca=3050