[Algorithm] 백준 2302 극장 좌석

백준 온라인 저지 2302 극장좌석

문제
problem inNout

백준 온라인 저지

이 문제는 VIP석을 기점을 구역을 나누어서 해당구역에서 가능한 경우의수를 구하고 각 구역에서 도출된 값을 곱하는 것으로 방향을 잡는다.
이 때 각 구역에서 발생하는 경우의 수를 구하는 것이 관건이다. 사실 어렵지 않게 구할 수 있다. 예를 들어 구역의 좌석수가 1개일 경우는 1가지, 2개일 경우는 2가지이다 3개일 경우는 2개인 경우에서 끝에 3번좌석을 붙인경우의 수와 2번좌석과 3번자석을 바꾼 경우의 수 이렇게 2가지로 나눌 수 있다. 여기서 2번좌석과 3번좌석을 바꾼 경우의 수는 그 전 단계에서 2번좌석과 1번좌석을 바꾸지 않은 경우에만 3번좌석과 2번좌석을 바꿀 수 있다. 왜냐하면 각 좌석은 2칸이상 이동할 수 없기 때문이다. 따라서 관계식을 찾아보면
dp[i]=dp[i-1]+dp[i-2]
즉 피보나치 수열의 형태를 띄는 것을 볼 수 있다. 이때 i는 좌석의 수이며 dp[i]는 좌석의 수가 i일때 얻어지는 경우의 수이다. 이를 이용해 각 구역사이의 좌석의 수를 구하고 이들을 모두 곱하면 원하는 값을 얻을 수 있다.

소스코드 C++

#include <iostream>
using namespace std;

int main() {

	int n;
	cin >> n;
	int* dp = new int[n + 1];
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {//[i] ->i는 좌석의 분할된 갯수
		dp[i] = dp[i - 2] + dp[i - 1];
	}

	int splitNum;
	cin >> splitNum;
	int* split = new int[splitNum + 2];
	split[0] = 0;
	split[splitNum + 1] = n + 1;
	for (int i = 1; i <=splitNum; i++)
		cin >> split[i];
	int result = 1;
	for (int i = 1; i <= splitNum + 1; i++) {
		int tempNum = split[i] - split[i - 1] - 1;
		result = result * dp[tempNum];
	}

	cout << result;
	return 0;

}

Java

import java.util.Scanner;

public class theaterSeat_2302 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] dp = new int[n + 1];//[i]->i는 좌석의 분할된 갯수
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 2] + dp[i - 1];

        int splitNum = sc.nextInt();
        int[] split = new int[splitNum + 2];
        split[0] = 0;
        split[splitNum+1] = n + 1;
        for (int i = 1; i <= splitNum; i++)
            split[i] = sc.nextInt();



        int result = 1;
        for (int i = 1; i <= splitNum + 1; i++) {
            int tempNum = split[i] - split[i - 1] - 1;
            result = result * dp[tempNum];
        }
        System.out.println(result);
    }
}

FEATURED TAGS

FRIENDS