백준 4811. 알약

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

4811번: 알약

 

 

dp 문제.

 

3차원 배열 [day][통에 남은 한 조각 갯수][통에 남은 반 조각 갯수] = 경우의 수  을 만든다. 

 

통에서 알약을 꺼냈을때 두 가지 경우가 있는데 한 조각 짜리를 꺼냈을때와 반 조각 짜리를 꺼냈을 때다. 

 

다음날 한 조각 짜리를 꺼내는 경우를 생각해보면 오늘 한조각 짜리가 통에 남아있는 경우에만 꺼낼수 있고, 한 조각 짜리를 꺼내면 통에 한조각 짜리가 1개 줄어들고 반 조각 짜리는 1 늘어나기 때문에 [day][W-1][H+1]에 경우의 수를 더해주면 된다. 

 

다음날 반 조각 짜리를 꺼내는 경우를 생각해보면 오늘 반조각 짜리가 통에 남아있는 경우에만 꺼낼수 있고, 반 조각 짜리를 꺼내면 통에 반 조각 짜리가 1개 줄어들기 때문에 [day][W][H-1]에 경우의 수를 더해주면 된다.