다이나믹 프로그래밍 문제! 경우의 수를 따져서 출력해야 하는데 n=1, n=2까지 직접 경우의 수를 따져보며 규칙을 발견하며 푸는 방식 n=0일땐 1 사자가 하나도 배치가 되어있지 않은 경우의 수도 하나의 경우로 친다고 했으므로. n=1일땐 3 oo, xo, ox 총 3가지 n=2일땐 7 1) n번째 줄이 모두 비어있는 상태 (oo) n=1 oo. xo. ox n=2 oo oo. oo -> 3가지 dp[n-1] * 1 : n번째 줄에는 oo 하나의 경우만 존재하고 있으므로 1를 곱하는 것 2) n-1번째 줄이 모두 비어있는 경우 (oo) n=1 oo. oo n=2 xo ox -> 2가지 dp[n-2] * 2 3) n-1, n번째 줄이 모두 채워져 있는 경우 (ox , xo) dp[n-1]-dp[n-2] ..
