반응형
1309
-
BOJ) 동물원 (1309, JAVA)알고리즘/백준 2020. 8. 24. 16:44
풀이 코드 라인을 보면 아주 간단한 문제라고 여겨지겠지만, 점화식을 도출하는 것이 어려웠다. 더 사실대로 말하자면, 혼자 도출하지 못했고 다른 풀이에서 점화식을 얻어왔다고 표현하는게 더 맞는 것 같다. 처음에는 Combination과 같은 경우를 찾는 식을 활용하는 방향으로 접근했다.하지만 어떤 식도 부합하는 것이 없었고, n=1 ~ n=4까지 직접 경우의 수를 찾아봤다. n=1 => 3n=2 => 7n=3 => 17n=4 => 41 위와 같이 경우의 수가 나왔다.위에서 유추할 수 있는 것은, dp[n] = dp[n-1]*2 + dp[n-2] 라는 식이다.n-1의 경우의 수 *2 + n-2의 경우의 수가 되는데, 왜 이 식이 성립하는지는 아직 명확하지 않다.n이 1씩 증가할 때마다, 2칸이 생기기 때문에..