[BOJ] 백준 1309 동물원 (JAVA)

[BOJ] 백준 1309 동물원 (JAVA)Algorithm/- Baekjoon2023. 12. 18. 12:00@Koben

Table of Contents

📑 문제

사자는 마주 보게 배치하면 안 되며, 한 마리도 존재하지 않는 경우도 하나의 경우의 수로 센다

동적계획법(DP)을 사용하면 시간도 아끼면서 풀 수 있다!

사실 본인도 점화식 세우는 법을 잘 모른다... 하지만 감이 안 잡히면 N의 수만큼 경우의 수의 수열을 만들어 보자!

일단 문제처럼 N*2 배열을 만들어보자!

(문제 조건에 성립하는 경우의 수)

N = 0 -> 1

N = 1 -> 3

N = 2 -> 7

N = 3 -> 17

N = 4 -> 41

이렇게 증가되는 수열이 만들어진다 이것을 점화식으로 세운다면

점화식 = fn = f(n-1)*2 + f(n-2) 이렇게 세울 수 있다. 즉 전값*2 + 전전값 이 현재값이다 이용해서 구현해 보자!

점화식을 세우고 DP 통해 구현한다면 쉽게 답을 맞힐 수 있을 것이다.

dp[0], dp[1]은 선언을 직접 해줘야 dp[2] 부터는 반복문으로 경우의 수를 얻을 수 있다

DP를 사용할 때는 초반 설정하는 값도 잘 설정해야 한다!

조건이 있는 수열은 점화식으로 세울 수 있다!

이러한 자신감을 가지고 차근차근 생각해 보니까 더 좋은 풀이가 나왔던 것 같다

DP랑 친해지기 진짜 힘들다 휴