2302번: 극장 좌석 www.acmicpc.net 이 문제는 한 줄로 되어있는 좌석에 사람들이 앉는 서로 다른 방법의 수를 구하는 문제이다. 이때 VIP 회원은 반드시 자기 좌석에만 앉아야 하고, 일반 회원은 양 옆의 사람끼리만 자리를 바꿀 수 있다. 예를 들어 5번 좌석에 앉은 일반 회원은 4번 좌석이나 6번 좌석에 앉을 수 있다. 하지만 3번 좌석이나 7번 좌석에는 앉을 수 없다. 이를 해결하기 위해서는 dynamic programming을 이용한다. 우선 각 i번째 좌석마다 그 좌석을 예약한 사람이 그 자리에 그대로 앉는 경우와, 예약한 사람 오른쪽에 있는 사람과 바꿔 앉는 경우를 각각 저장하는 배열을 i번째 entry로 하는 배열 dp를 만든다. 초기값으로는 모두 0을 지정하되 dp[1][0]은..
