[BOJ][DP] 1309. 동물원

문제 -> https://www.acmicpc.net/problem/1309

코드 자체는 짧지만 

아이디어가 중요한 문제. 

단순하게 문제를 생각해야 비로소 답이 보인다. 

한 사자가 놓여져있을 때, 

그 놓인 사자의 가로, 세로의 방향으로는 사자를 놓을 수가 없으므로

아래와 같이 대각선으로 놓든, 아무 사자도 놓지 않는 경우가 있다.

N번째줄 칸에 칸이 놓일 수 있는 경우는 

N-1번째줄 칸의 사자 배치의 상태에 따라 달라진다.

위 그림을 보면 알아 챌 수도 있지만,

N-1번째줄에 어떤 한 칸이 있으면 

그 밑에 사자를 배치할 수 있는 경우의 수는 각각 2개씩.

N-1번째줄에 아무 사자가 없으면 그 밑에 배치할 수 있는 경우는 3개.

즉, 경우를 두 개로 나누어서 생각해야 한다는 것.

그렇다면 

점화식은 

dp[i] = dp[i-1] * 2 + dp[i-2]가 되겠다.

일단 위에 칸이 있던 없던 2씩 곱하고,

이제 칸이 없는 경우인 dp[i-2]를 더하면 끝이다.

아, 그리고 문제에서 주어진 

나머지 연산을 하는것을 잊지 않기를.

모두 만족한다. 

소스(Github)