다이나믹 프로그래밍 썸네일형 리스트형 [백준] 1309 동물원 / 자바(Java) 문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 해설 dfs와 같은 탐색으로 해결하기에는 N의 길이가 너무 길다(답을 9901로 나눈 나머지를 출력하라는 부분도 값이 크게 되리라는 예상이 된다) 따라서 DP를 사용해 이전의 경우의 수에서 가능한 가능성을 구하는 점화식의 형태로 문제를 해결한다. arr[i][j]에서 i 는 사자우리의 세로번째의 수, j는 0~2까지 각각 사자가 들어가지 않는 경우, 왼쪽칸에 들어간경우, 오른쪽 칸에 들어간 경우를 나타내어 arr[i][j]는 i번째에 각 가능성이 될 경우의 수가 들어가게 된다. 사자우리는 바로 이전 번째에서만 영향을 받아 a.. 더보기 이전 1 다음
