가취공부하자

[백준] 1309번 동물원 c++

문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제풀이 dp를 사용하는 문제이다. 각 행에서 나오는 경우의 수는 총 3가지이다. 1. 행에 사자를 배치하지 않은 경우 2. 행의 오른쪽에 사자를 배치한 경우 3. 행의 왼쪽에 사자를 배치한 경우 따라서 n이 2이상일때 dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] //i 행에는 사자가 배치되어 있지 않으므로 1,2,3 경우의 수 모두 가능하다 dp[i][1] = dp[i - 1][0] + dp[i - 1][2] //i행에 사자가 오른쪽에 배치되어 있으므로 1,3의 경우만 가..
알고리즘/백준 2021. 3. 24. 04:40
이전 Prev 1 Next 다음