[백준 4811번] 알약 (java)

4811번: 알약

 

다이나믹 프로그래밍으로 문제를 해결하였다.

메모이제이션을 위해 3차원 dp배열을 생성했다. 

int[][][] dp = new int[2*N+1][2*N+1][N+1];

첫번째 인덱스는 몇일이 지났는지를 의미하고, 두번째 인덱스는 현재 시점에서 반알짜리 알약의 개수, 세번째 인덱스는 한알짜리 알약의 개수를 의미한다.

 

dp[t][h][w] : t일이 지났을 때, 반알짜리 알약의 개수가 h개이고, 한알짜리 알약의 개수가 w개일 때 가능한 모든 문자열의 개수

 

점화식을 세우면 아래와 같다.

dp[t][h][w] = dp[t-1][h+1][w] + dp[t-1][h-1][w+1]

t일이 지났을때 반알짜리 알약의 개수가 h개, 한알짜리 알약의 개수가 w개가 되기 위해서는

 

  1. t-1일에 반알짜리 알약 h+1개와 한알짜리 알약 w개가 있을 때, 반알짜리 알약을 먹는 경우

     dp[t-1][h+1][w]

 

  2. t-1일에 반알짜리 알약 h-1개와 한알짜리 알약 w+1개가 있을 때, 한알짜리 알약을 먹는 경우

     dp[t-1][h-1][w+1] 

 

이렇게 두 가지 경우가 존재한다.

 

1번의 경우에는 반알짜리 알약은 h+1개에서 h개로 줄어들고, 한알짜리 알약은 그대로이다.

따라서 t일째 되는 날, 반알짜리 알약은 h개, 한알짜리 알약은 w개가 된다.(dp[t][h][w])

 

2번은 한알짜리 알약은 w+1개에서 w개로 줄어들고, 한알짜리 알약을 반으로 쪼개서 하나는 먹고 하나는 남으므로 반알짜리 알약은 h-1개에서 h개로 하나 증가한다. 따라서 t일째 되는 날, 반알짜리 알약은 h개, 한알짜리 알약은 w개가 된다.(dp[t][h][w])

 

따라서, 위의 점화식을 바탕으로 삼중 반복문으로 메모이제이션을 하면, 

2*N일째 되는 날 나타낼 수 있는 총 문자열의 개수를 구할 수 있다.

 

전체 코드 :