[백준 1309번] 동물원 - java

문제 설명

1. 2xn크기의 우리를 갖는 동물원이 있다.

2. 사자를 넣는데, 사자의 양옆위아래에는 다른 사자가 있으면 안된다.

3. 모든 사자를 배열하는 방법을 찾는다. 사자의 수는 제한이 없고 아무도 없는 경우도 방법으로 친다.

 

풀이 과정

 1. DP를 통해서 풀 수 있다.

 2. 나는 DP의 경우 한번 n이 3이나 4가 될 때 까지는 무작정 경우의 수를 구하는 것이 쉽게 풀 수 있는 방법이라 생각한다. 그래서 그냥 방법을 구해 보았다.

 

우리 집에 있는 무서운 사자를 우리에 넣어보도록 하겠다.

먼저 2x1의 크기 우리에 사자가 배열되는 경우는 다음 세 가지에 해당한다.

 

그럼 다음으로 2x2의 우리에 사자를 넣는 경우는 어떻게 될까?

먼저 가장 왼쪽 ox의 경우(o는 사자, x는 빈칸)

이렇게 다음 우리가 생성될 것이다.

그리고 가운데의 xo의 경우는

이렇게 우리가 만들어 질 것이고

마지막 xx의 경우는

이런 식으로 우리가 생성될 것이다.

 

여기서 현재 우리의 위칸에 생성되는 우리를 확인해 보면, 한 가지를 알 수 있다.

xo우리 위에는 xx와 ox가

ox우리 위에는 xx와 xo가

xx우리 위에는 xx와 xo, ox우리가 생성될 수 있다는 것이다.

 

즉 n번째 우리 위인 n+1우리를 보면

xo우리의 생성은 xo, xx의 위에

ox우리의 생성은 xo, xx의 위에

xx우리의 생성은 모든 우리 위에서 이루어 진다는 것을 알 수 있다.

 

여기서 식을 하나 세우자면 현재 생성될 우리에 대해

xx우리의 총 개수는 이전 모든 우리의 수

xo우리의 총 개수는 이전 우리의 xx, ox의 개수

ox우리의 총 개수는 이전 우리의 xx, xo의 개수

라는 것을 알 수 있다.

 

이를 통해 쉽게 답을 구해낼 수 있다.

코드