[정올][다이나믹] 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가지 종류가 가능

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

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