[Python] 백준 1309번 : 동물원

1309번: 동물원

[ 문제 조건 ]

• 2 * N 배열의 동물원 우리
• 사자를 배치할 때 가로 세로로 붙어있으면 안됨
• 사자가 한마리도 없는 경우도 1가지 경우로 침

[ 해결순서 ]

1. 처음엔 기존의 dp 같은 방식으로 풀려고 시도해 배열의 각 칸에 숫자를 부여해서 조건에 맞는 조합으로 값을 계산해서 구하려고했다. 뭔가 규칙이 보이는 것 같다가도 막상 식을 못세우겠어서 조금 헤매다 결국 구글의 도움을 좀 받았다. ( 삽질을 하고있단 느낌이 .. )
2. 첫번째 줄에 경우를 3가지로 나눠서 계산을 해야한다. *4번 줄 참고
3. 경우의 수를 나눈 후 제일 작은 예시인 2 X 2 배열일 때를 직접 적어가며 규칙을 찾아보려했다.
4. 사진을 참고하면 이해가 빠르겠지만,
   1. 한마리도 두지 않는 경우는 ( 두지 않는 경우, 왼쪽, 오른쪽 )
   2. 한마리 왼쪽에 두는 경우 ( 두지않는경우, 오른쪽 )
   3. 한마리 오른쪽에 두는 경우 (두지않는경우, 왼쪽 )
5. 이런식으로 경우의 수를 계산해 누적 값을 계속 갱신해가면서 더하면 해답이다.

처음 시도한 풀이

✏️한줄평

: 뭔가 쉬워보여서 풀 수 있을 것 같았는데 나는 모든 경우의 수를 찾아 헤매느라 규칙을 찾지 못했다. 해답의 아이디어는 첫째줄의 경우의 수를 기준으로 모든 경우가 나뉘는 것으로 방향을 잡고 해야했는데.. dp는 늘 새롭다.. 😅

---

코드