[정올][다이나믹] 1848 극장좌석
극장좌석문제는 다이나믹 프로그래밍으로 풀이가 가능하다. 전제조건은 좌우 한칸으로는 이동이 가능하다. 좌석이 2개일 경우 아래의 두개의 경우가 가능1, 22, 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, 22, 1 -> 2, 1, 3좌석이 4개일때는 좌석이 3개인 경우에서 끝자리가 3인 경우는 4와 교환이 가능하기 때문에 4가지 경우가 나오고, 2인 경우는 4와 교환이 불가능하이 끝에 4가 붙는 ..
2017. 4. 11.