백준 2302번 극장 좌석 [DP] :: 마이구미

이번 글은 백준 알고리즘 2302번 "극장 좌석" 문제를 다뤄본다.

이 문제의 키워드는 동적계획법(DP), 피보나치, 곱의 법칙이다.

문제를 보자.

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 써 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

한 좌석을 기준으로 왼쪽 1칸이나 오른쪽 1칸으로 VIP 좌석이 아닌 좌석으로 이동할 수 있다.

이 문제는 곱의 법칙을 활용할 수 있다.

중등 수학에서 나오는 법칙으로써, 합의 법칙과 곱의 법칙이 존재한다.

합의 법칙과 곱의 법칙은 경우의 수를 구하는 방법이다.

합의 법칙은 두 사건 A, B가 있을 때, 동시에 일어나지 않았을 경우 두 사건의 경우의 수를 각각 더한다.

곱의 법칙은 두 사건 A, B가 있을 때, 동시에 일어날 경우 두 사건의 경우의 수를 곱한다.

자세한 건 관련 링크를 참고하자.

VIP 좌석이 4, 7이 주어졌을 경우, 위와 같이 {1,2,3} , {5,6}, {8,9} 의 경우가 나온다.

이 경우들이 동시에 일어나기 때문에 각각 곱해주면 정답을 구할 수 있다.

점화식은 어떻게 구할 수 있을까?

하나의 좌석을 기준으로 좌석을 옮기는 경우는 2가지다.

1. 좌석을 옮기는 경우. - dp[n-2]

2. 좌석을 옮기지 않는 경우. - dp[n-1]

이를 활용하여 점화식 dp[n] = dp[n-1] + dp[n-2]  만들 수 있다.

정확한 이해를 위해서는 직접 경우의 수를 만들어보면 된다.

위 그림을 보자.

n = 2 의 경우 2가지

n = 3 의 경우 3가지

n = 4 의 경우 5가지

계속해서 구해보면 n = 5 의 경우는 8가지... 피보나치 수열을 볼 수 있다.

n = 3의 경우에서 4를 붙여보면 n = 4의 경우 중 3가지를 포함하는 것을 볼 수 있다.

4를 붙인다는 것은 좌석을 옮기지 않는 경우를 뜻한다.

나머지 2가지는 n = 2인 경우 좌석을 옮기는 경우가 된다.

위 그림에서 이어진 선들을 보면 이해가 갈 것이다.

for(int i=2;i<=n;i++) {
    dp[i] = dp[i-1] + dp[i-2];
}

int tmp = 0;
for(int i=0;i<m;i++) {
    int k = sc.nextInt();
    ans *= dp[k-tmp-1];
    tmp = k;
}

ans *= dp[n - tmp];

전체 소스는 아래 Github URL을 통해 확인하길바란다.

백준 알고리즘 2302번 문제 "극장 좌석" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/dp/2302.java