다이나믹 프로그래밍
이문제는 다이나믹 프로그래밍으로 풀수 있다.
사자배치를 했을떄와 안했을떄를 o와 x 로 나누면
xx다음엔 xx ox xo
ox다음엔 xx xo
xo다음엔 xx ox
가 나올수 있다.
그러므로 이것을 다이나믹 dp로 공식을 세우게 된다면
dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2]
dp[n][1] = dp[n-1][0] + dp[n-1][2]
dp[n][2] = dp[n-1][0] + dp[n-1][1] 로 나오게된다.
코드와 시키면 이렇게 나오는데 나누기하는것을 뺴먹어서 틀렸었다.
문제를 잘 읽도록 하자.