키베이루's diary

1) 문제설명 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 2) 아이디어 처음에는 2차원 배열로 dp를 설정하여 마릿수 / n층으로 표를 그려 규칙을 찾으려고 했으나 규칙을 찾기가 매우 어려웠다. 따라서 이를 해결하기 위해 dp [n층][사자를 배치하지 않음/ 사자를 왼쪽에 배치/ 사자를 오른쪽에 배치]로 나누어서 생각하였다. 처음 dp [1][0] = 1층에 사자를 배치하지 않는 경우의 수는 = 1이다 마찬가지로 dp [1][1] = 1층에 사자를 왼쪽 배치할 경우의 수 = dp [1][2] = 1층에 사자를 오른쪽 배치할 경우의 수 = 1 이후 2층에 사자를 배치할 경우..