Baekjoon 1309 동물원 JAVA

https://www.acmicpc.net/problem/1309

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201309

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 2*N의 배열에 사자를 놓을 수 있는 경우의 수를 구하는 문제다.

단, 가로 세로에 붙어있게 사자를 놓을 순 없고, 한 마리도 배치 안 하는 경우도 하나의 경우로 친다

​

문제를 보곤 딱 dp 문제라고 생각했고 dp를 이용해서 문제를 해결했다.

​

처음에 2*N 표를 만들어서 표를 채워보았는데 해당 열 칸에 아무것도 안 들어간 경우의 수도 체크를 해줘야 해서

​

3*N 배열을 통해서 문제를 해결했다

​

1행에는 해당 열에 사자를 한 마리도 안 놓는 경우의 수를 적었고, 즉 앞 열의 모든 경우의수 합이 그대로 오면 된다.

2행에는 해당 칸에 대한 경우의 수를 넣어주는데 이제 이 부분은 앞 열에 아무것도 오지 않는 경우의 수와,

대각선 칸에 사자가 있는 경우의 수에 대해 넣어주면 되고 3행도 마찬가지로 진행하면 된다.

​

점화식으로 하면 아래와 같아지며, 출력 부분은 그냥 배열 크기를 한 칸 늘려 입력값 다음 칸의 \

첫행을 출력해 주었다.

dp[0][i] = dp[0][i-1]+dp[1][i-1]+dp[2][i-1]

dp[1][i] = dp[0][i-1]+dp[2][i-1]

dp[2][i] = dp[0][i-1]+dp[1][i-1]