문제 링크 : www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이 문제에 빠진 설명이 있는데, 한 칸마다 동물은 한 마리씩 배치시킬 수 있다. 문제 풀이는 다음과 같다. 1. 한 줄에 사자를 배치시키는 방법은 3가지가 있다. (1) 아예 배치를 안 시킴 (2) 첫 번째 칸에 배치 (3) 두 번째 칸에 배치 2. 사자는 가로로 세로로 붙어서 배치시킬 수 없다. 가로에 붙어서 배치시킬 수 없다는 말은 각 줄마다 2칸 모두에 사자를 한 마리씩 배치시킬순 없다는 뜻이다. 세로에 붙어서 배치시킬 수 없다는 말은, 예를 들어 n번째 줄의 첫 번째 칸에 배치시켰을 경우, n-1번째 줄의 첫 번째 칸과 n..
