dynamic programming 1

* 틀린 내용이 있을 시 지적 부탁드립니다.

얼마나 포스팅을 할진 모르겠지만... 일단 만들어봤습니다.  제목은 뭘로 할까 하다가 그냥 카테고리에 맞게지었습니다.

문제는 더블릿 21 dynamic programming에 있는 apple_catching입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/apple_catching/apple_catching.php?pname=apple_catching

간단히 문제를 설명하자면 

1. 2개의 나무에서 1분마다 둘 중 하나의 나무에서만 사과가 하나씩 떨어집니다.

2. 원숭이는 둘 중 하나의 나무 밑에 있다가 떨어지는 사과를 먹을 수 있고 이미 떨어진 사과는 먹지 못합니다.  (이전 시간에 받지 못해 떨어진 사과를 다음 시간에 이동해서 줏어 먹을 수 없습니다.)

3. 원숭이가 나무를 왔다갔다 할 수 있는 횟수는 제한되어 있습니다.

4. 제한된 횟수내에서 이동하여 사과를 제일 많이 받아 먹을 때 그 개수를 출력하면 됩니다.

dp이니 dp 배열을 하나 만듭니다.  dp는 이전 값들의 결과로 다음 값을 도출해내는 방식인데 저는 배열 횡은 분, 열은 이동 횟수로 표현하겠습니다.  분이 지나갈 수록, 이동 횟수에 따라 값들이 쌓이는 모양입니다.  

그럼 [1001][31]이 되겠습니다.  인덱스는 문제에 맞게 1부터 시작하기 위해서 공간을 저렇게했습니다.

여기까지 하면 다음은 배열을 채워주면 됩니다.

예제를 가지고 설명하겠습니다.

아래는 dp 배열입니다.

먼저 0분일 때는 아무것도 먹지 못했으니 dp 배열은 0으로 놔둡니다.

(분↓) 0    1    2 (이동횟수)

0       0    0    0                       (dp 배열)

//1분이 지난 후입니다.  1분이 지났을 때 이동하지 않으면 1번 나무에 있을 것이고 이 때 사과는 2번 나무에서 떨어지므로 [1][0]은 0이 될 것입니다.

반면 한번 이동해서 2번나무로 가면 떨어지는 사과를 받아 먹을 수 있으니 한 개 먹을 수 있고 2번 이동해서 제자리로 오면 역시 0개입니다.

1    0    1    0

//2분이 지난 후입니다.  한번도 이동하지 않으면 2분에 떨어지는거 하나 먹을 수 있고([2][0]), 한번 이동하는 경우 2분째에 있는 걸 먹던지 1분째에 있던걸 먹던지 하나 먹을 수 있습니다.  2번 이동하는 경우 1분째에 것 이동해서 먹고 2분째에 것도 이동해서 총 2개를 먹을 수 있습니다.

2    1    1    2

//3분이 지난 후입니다.  제자리에 있으면 2, 3번째 사과 2개를 먹을 수 있고, 1번 이동하면 1분꺼 or 2분꺼 하나를 먹을 수 있습니다.  2번 이동하면 1, 2, 3분꺼 다 먹을 수 있습니다.

3    2    1    3

//이제 규칙을 찾아야 합니다.  1번 이동할 경우 1분에 이동할 수도, 2분에 이동할 수도 있는데 먹을수 있는 최대 사과 개수를 배열에 넣어줘야 합니다.  매번 1분에 이동했을 때, 2분에 이동했을 때 사과의 개수를 구해서 넣어줄 순 없습니다.  dp에서는 이런 경우 바로 전의 값을 이용해서 계산 할 수 있습니다.  

예를 들어 4분에 1번 이동했을 경우 이용할 수 있는 값은 3분에 0번 이동했을 때와 3분에 1번 이동했을 때 입니다.  3분에 2번 이동했는데 4분에 1번 이동했다는건 모순이됩니다.  그럼 4분에 1번 이동했을 때는 3분에 0 or 1번 이동했을 때의 최대값에서 계산해주면 됩니다.  

그리고 해당하는 시간에 어느 위치로 이동 했을 때 그 위치에서 사과가 떨어지면 +1을 해줍니다.

4분에 0번이동은 3분의 0번이동에서 계산하는데 4분째에는 2번나무에서 사과가 떨어지기 때문에 +1을 해주지 않습니다.  반면 4분에 1번이동은 3분의 0 or 1번이동 중 많은 사과를 먹은 쪽을 택하고 1번이동했을 시 2번나무에 있는 한편 2번나무에서 사과가 떨어지므로 +1을 해줍니다.  

4    2    3    3

이런 식으로 7분 까지 채워주고 7분 째에서 가장 많이 사과를 먹었을 때 그 개수를 출력해주면 됩니다.