[백준 2240번] 자두나무 (java)

2240번: 자두나무

 

다이나믹 프로그래밍을 이용하여 풀이하였다.

dp 배열을 3차원 배열로 만들었다.

int[][][] dp = new int[T+1][3][W+1]

int[][][] dp = new int[자두가 몇번째 떨어지는가][자두(사람이름)이 어느 위치에 있냐][이동횟수]

 

dp[t][1][w] : t번째 자두가 떨어질 때, 1번 나무에서 떨어지는 경우 여태껏 w만큼 이동했을 때의

                얻을 수 있는 자두 최대값

dp[t][2][w] : t번째 자두가 떨어질 때, 2번 나무에서 떨어지는 경우 여태껏 w만큼 이동했을 때의

                얻을 수 있는 자두 최대값

 

예를 들어, dp[n][1][3]에서 dp[n][1]는 n번째 떨어지는 자두가 1번 나무에서 떨어질 때이며

마지막 인덱스인 3은 자두(사람이름)이 이동한 횟수를 의미한다.

마찬가지로 dp[n][2][3]에서 dp[n][2]는 n번째 떨어지는 자두가 2번 나무에서 떨어질 때이며

마지막 인덱스인 3은 자두(사람이름)이 이동한 횟수를 의미한다.

 

 

점화식은 다음과 같이 세울 수 있다.

 

t번째 자두가 떨어질 때, 1번 나무에서 떨어지는 경우,

• dp[t][1][w] = Math.max(dp[t-1][1][w], dp[t-1][2][w-1]) + 1

      dp[t][1][w] : t번째 자두가 떨어질 때, 자두(사람)가 1번에 있다고 가정

      t-1번째 자두가 떨어졌을 때 자두가 1번 위치에 있었고, 이동횟수가 w번 이었을때 (dp[t-1][1][w])

      t-1번째 자두가 떨어졌을 때 자두가 2번 위치에 있었고, 이동횟수가 w-1번 이었을때 (dp[t-1][2][w-1])

      둘 중에 더 자두를 많이 주었을 때를 선택한다.

 

      그리고 +1을 하는 이유는 이번에(t번째에) 자두가 1번 나무에서 떨어지고 자두(사람)도 1번에 있는 

      경우이므로 자두 하나를 더 얻기 때문이다.

      

• dp[t][2][w] = Math.max(dp[t-1][1][w-1], dp[t-1][2][w])

      dp[t][2][w] : t번째 자두가 떨어질 때, 자두(사람)가 2번에 있다고 가정

      t-1번째 자두가 떨어졌을 때 자두가 1번 위치에 있었고, 이동횟수가 w-1번 이었을때 (dp[t-1][1][w-1])

      t-1번째 자두가 떨어졌을 때 자두가 2번 위치에 있었고, 이동횟수가 w번 이었을때 (dp[t-1][2][w])

      둘 중에 더 자두를 많이 주었을 때를 선택한다.

 

      이번에는(t번째에) 자두가 1번 나무에서 떨어지고 자두(사람)는 2번에 있으므로 자두를 얻을 수 없기

      때문에 +1을 해주지 않는다.

 

 

 

t번째 자두가 떨어질 때, 2번 나무에서 떨어지는 경우,

• dp[t][1][w] = Math.max(dp[t-1][1][w], dp[t-1][2][w-1]) 

      dp[t][1][w] : t번째 자두가 떨어질 때, 자두(사람)가 1번에 있다고 가정

      t-1번째 자두가 떨어졌을 때 자두가 1번 위치에 있었고, 이동횟수가 w번 이었을때 (dp[t-1][1][w])

      t-1번째 자두가 떨어졌을 때 자두가 2번 위치에 있었고, 이동횟수가 w-1번 이었을때 (dp[t-1][2][w-1])

      둘 중에 더 자두를 많이 주었을 때를 선택한다.

 

      이번에는(t번째에) 자두가 2번 나무에서 떨어지고 자두(사람)는 1번에 있으므로 자두를 얻을 수 없기

      때문에 +1을 해주지 않는다.

 

• dp[t][2][w] = Math.max(dp[t-1][1][w-1], dp[t-1][2][w]) + 1

      dp[t][2][w] : t번째 자두가 떨어질 때, 자두(사람)가 2번에 있다고 가정

      t-1번째 자두가 떨어졌을 때 자두가 1번 위치에 있었고, 이동횟수가 w-1번 이었을때 (dp[t-1][1][w-1])

      t-1번째 자두가 떨어졌을 때 자두가 2번 위치에 있었고, 이동횟수가 w번 이었을때 (dp[t-1][2][w])

      둘 중에 더 자두를 많이 주었을 때를 선택한다.

 

       +1을 하는 이유는 이번에(t번째에) 자두가 2번 나무에서 떨어지고 자두(사람)도 2번에 있는 

      경우이므로 자두 하나를 더 얻기 때문이다.

 

 

소스코드 :