백준 1309 자바스크립트

[백준] 1309번 동물원 - JavasScript(NodeJS)

문제 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 DP(동적 계획법) 문제이므로 DP로 접근한다. 다음 N * 2 행렬의 N번째 행만을 기준으로 생각하자. N번째 행에 사자가 없다면 E, 사자가 있다면 I로 나타내본다. N=1일 때, 경우의 수는 E=1, I=2 로 총 3이다. N=2일 때, N=1의 경우의 수 각각에 2번째 행이 생성되었을 때를 생각하면 E=1로부터 E=1, I=2 생성 I=2로부터 각각 E=1, I=1이 생성되므로 총 E=2, I=2가 생성 그러므로 N=2의 경우의 수는 E=1+2, I=2+2로 총 7이다. 계속해서 진행하면, N=3일 때, N=2의 경우의 수 각각에 3번째 행이 생성되므로 E=3으로부터 E=3, ..