Suhwanc

백준 1309번 동물원

문제 링크 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 다이내믹 프로그래밍 문제입니다! 2X1 칸에 사자를 배치하는 경우는 왼쪽 사자 오른쪽 사자 사자 없음 세 가지이며, 사자들은 가로,세로에 붙어있을 수 없다. 각각의 경우를 0,1,2로 표현했을 경우 d[i][j] = i칸에 j상태의 사자가 있을 경우 사자 배치의 경우의 수 라고 표현 가능하며 각각 d[i][0] = d[i-1][1] + d[i-1][2] d[i][1] = d[i-1][0] + d[i-1][2] d[i][2] = d[i-1][0] + d[i-1][1] + d[i-1][2] 이다. 따라서 정답은 d..