[Java] 다이나믹 프로그래밍 (동물원)

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

1309번: 동물원

 

집에 누워있으면 진짜 안될 것 같은 위기감을 느끼고 집 앞 2분 거리 카페에 나와서 문제를 풀었다.

 

다이나믹 문제를 풀려고 푼 게 아니라 내가 좋아요 누른 문제집을 거의 다 풀고 2개 남아서 그중 하나를 골랐는데 풀어보니 dp였다. 이제 문제를 보기만 하면 dp가 생각이 난다

 

사실 문제를 풀려고 카페를 갔던 게 아니라서 펜과 종이가 없어서 그림판으로 풀었다.

 

 

 

 

 

작은 수를 놓고 좀만 끄적이다 보면 바로 규칙이 나온다.

dp는 늘 규칙찾는 퍼즐 푸는 것 같다

 

 

1. [][0]에는 이전까지의 합을 누적해서 저장

2. [][1]에는 마지막 우리가 비어있는 경우의 수 저장

3. dp[N][0] =

• N-1 에서의 경우의 수 : 여기에 마지막에 비어있는 우리를 배치
• (N-1에서 마지막이 비어있는 경우의 수) * 2  = 여기에는 오른쪽 우리, 왼쪽 우리 경우의 수가 2개니까 2를 곱해주자
• (N-1의 경우의 수) - (N-1에서 마지막 우리가 비어있는 경우의 수)  = 나머지 경우 

 

를 다 더하면 된다.