목록백준1309번 (1)

HS_development_log

백준 1309번 - 동물원 / Java

문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 인접한 곳에 사자를 배치하면 안 되는 문제. 배치하지 않았을 때, 왼쪽에 배치했을 때, 오른쪽에 배치했을 때의 경우의 수를 모두 더해주면 정답을 구할 수 있다. 9901로 나눈 나머지를 구해줘야 하므로 나머지 연산을 적용해서 정답을 적용한다. 알고리즘 사자를 n번째 줄 i번째칸에 배치하는 경우의 수를 dp[n][i]로 정의한다 dp[n][0] 는 사자를 0번째 칸에 배치하는 경우의 수이다. 이때 dp[n-1]의 1번째 칸과, 2번째 칸에 배치하는 경우의 수, 그리고 배치하지 않는 경우의 수를 더해주면 된다. 나머지 연산을 해..
Algorithm-백준/다이나믹 프로그래밍 2020. 1. 19. 22:21
이전 Prev 1 Next 다음