BOJ 2240 자두나무(C++)

자두나무 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1307	541	386	39.630%

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

예제 입력 

7 2
2
1
1
2
2
1
1

예제 출력 

6

힌트

알고리즘 분류

• 다이나믹 프로그래밍

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include    <cstdio> #include    <algorithm> #define max(x,y) ((x)>(y)?(x):(y)) #pragma warning(disable:4996)   int D[1111][33][3]; int JADU[1111][3]; int main() {     int T, W;     scanf("%d%d", &T, &W);       int tmp;     for (int i = 1; i <= T; ++i)     {         scanf("%d", &tmp);         JADU[i][tmp] = 1;     }       // i초 j번 이동 k위치     D[1][0][1] = JADU[1][1];     D[1][1][2] = JADU[1][2];     int res = 0;     for (int i = 2; i <= T; ++i)     {         for (int j = 0; j <= W; ++j)         {             D[i][j][1] = max(D[i - 1][j][1], D[i - 1][j - 1][2]) + JADU[i][1];             D[i][j][2] = max(D[i - 1][j][2], D[i - 1][j - 1][1]) + JADU[i][2];             res = max(res, D[i][j][1]);             res = max(res, D[i][j][2]);         }     }     printf("%d", res);     return 0; }

다이나믹 프로그래밍. 요즘 다이나믹 프로그래밍 문제를 부쩍 많이 푸는 것 같다. 

T와 W가 주어진다. 우선 점화식을 세워본다. 

D[T][W]는 T초 때 W만큼 움직였을 경우의 최대로 받을 수 있는 자두 수라고 한다면 

D[i][j] 는 D[i-1][j] + 바뀌지 않은 위치의 자두 or D[i-1][j-1] + 바뀐 위치의 자두가 된다. 

그러면 D에 현재 자두의 위치도 저장을 해야 풀기가 편해질 것 같아서 3차원 배열로 바꿔보았다. 

D[i][j][k] 는 i초 때 j번 움직였을 경우 k인 위치에서의 받을 수 있는 자두의 최대값이라고 설정하면 

28~29번 줄과 같은 식이 나온다. 

추가로 이런 점화식을 세웠을 때 답은 

D[T][W][0]이나 D[T][W][1]이 아닌 

D[T]일 떄의 모든 값이 후보가 될 수 있다는 것이다. 

최대 W번 이동이 가능한 것일 뿐 이동하지 않을 수도 있기 때문이다. 

결국 문제의 답은 

D[T][0~W][1~2]중 하나이다. 

문제를 풀 때는 res를 for loop 내부에서 계속 연산했는데 이제보니 비효율적인것 같다. i가 T일때만 연산하면 될 것 같다..