CEO

문제 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제 풀이 이 문제는 위의 그림을 이해한다면 쉽게 점화식을 세울 수 있다. 처음에 N이 1일 경우, 사자가 존재하지 않을 경우와 사자가 왼쪽에 존재할 경우, 사자가 오른쪽에 존재할 경우가 각 1개씩이라는 것을 알 수 있다. N이 2가 되면 추가된 공간에 사자가 없거나, 사자가 왼쪽에 있거나, 사자가 오른쪽에 있을 경우의 수를 찾아야 한다. 새로운 공간에 사자가 없을 경우 같은 라인에 사자가 겹치거나, 모두 없어도 상관 없으므로 사자가 없는 경우, 왼쪽에 있는 경우, 오른쪽에 있는 경우를 모두 더한다. 이와 달리 사자가 왼쪽이나 오른쪽에 가기 위해서는 N - 1에 사자가 없거나, N - 1의..