알고리즘
DP를 정의 하는 방법
문제 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 재정의 경우의 수를 활용하여 풀려고 하니 쉽지 않았다. 단순 곱사건(동시에 일어나는 사건)이 아니라, 합사건도 같이 일어나기 때문이다. 이는 완전 탐색을 요구하고, 상태 공간의 중복이 발생한다. 그냥 DP를 사용하려고 하니, 상태 공간의 정의가 마음에 들지 않았다. 손으로 작성 해 보니 어떤 상태 공간을 사용할지 찾을 수 있었다. 역시 DP각은 손으로 써서 봐야 잘 보인다. 재귀 함수로 문제 정의하기 완전 탐색을 해야함을 인지 했으니, 일단 재귀 함수로 간단하게 정의를..
