백준) 2240 자두나무

2240. 자두나무

문제

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

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(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. 접근

두 나무 중에 내 위치를 w번 갈아탈 수 있다. t초 동안 자두는 t개 떨어지며,

매 초마다 두 나무 중에 자두를 떨궈줄 나무가 입력으로 주어진다.

t번 갈아탈 수 있다면 모두 받아먹을 수 있겠지만, w번으로 갈아탈 수 있는 기회가 한정된다.

그러면 우리는 어떤 전략으로 임해야 최대한 많은 자두를 받아먹을 수 있을까?

2. 풀이

전략을 생각해내기 보다 걍 컴퓨터에게 계산을 시키기로 하자.

심플함이 잘 팔리므로, 다이나믹 프로그래밍을통한 메모이제이션으로 모든 경우를 빠르게 확인해버리는 것이다.

얼마나 빠른지가 중요할텐데, 시간은 DP 배열의 크기에 비례한다.

문제의 변수는 세가지다 : 시간, 위치를 바꾼 횟수, 나의 위치

무언가 전략이 있다면 (최대 갯수가 세 가지 변수보다 적은 변수로 결정난다면) 더 작은 배열로 가능하겠지만, 나는 생각이 안나므로,

삼차원 배열로 DP 배열을 정의하도록하자.

DP[현재시간][현재 나의 위치][자리바꾼 횟수] = 현재 상황이 이러저러 할 때, 지금 상황부터 받아 먹을 수 있는 자두의 최대 갯수

정의 덕분에 함수 정의도 술술 풀린다.

func(int now, int pos, int cnt) = DP[now][pos][cnt] 를 계산해주는 함수.

나머지 할 일은 점화식을 세워주기만 하면된다. 계산은 컴터가 다 해준다.

자두를 받아먹는 경우는 다음 여섯가지로 나눠진다.

1. 현재 시간에 나의 위치와 자두가 떨어질 위치가 같다.

1-1 위치변경의 기회가 남았다.

1-1-1. 그래서 자리를 바꾸지 않고 1개 챙길 수 있다.

1-1-2. 자리를 바꾸고 후일을 도모한다.

-> max(func(now + 1, pos, cnt) + 1, func(now + 1, pos ^ 1, cnt + 1));

1-2 자리바꿈의 기회를 다 써버려서 가만히 있는다 -> 1개 챙긴다.

-> func(now + 1, pos, cnt) + 1;

2. 현재 시간에 나의 위치와 자두가 떨어질 위치가 다르다.

2-1 위치변경의 기회가 남았다.

2-1-1. 그래서 자리를 바꾸지 않고 후일을 도모한다.

2-1-2. 자리를 바꾸고 1개 챙긴다.

-> max(func(now + 1, pos, cnt), func(now + 1, pos ^ 1, cnt + 1) + 1);

2-2. 자리바꿈의 기회를 다 써버려서 가만히 있는다 

-> func(now + 1, pos, cnt);

케이스별로 함수를 호출해주고, 정답을 꾸려나가면 된다.

기저사례는 now가 T를 넘어가버리는 경우로, 정의에 따라 0을 리턴해야한다.

케이스를 더 효율적으로 나눌 수도 있겠다.

3. 코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int t, n, i;
int arr[1001];
 
int dp[1001][2][30];
 
int func(int now, int pos, int cnt) {
    if (now == t + 1)
        return 0;
    
    int& ref = dp[now][pos][cnt];
    if (ref != -1)
        return ref;
 
    if (pos == arr[now]) {
        int a1 = 0, a2 = 0;
        if (cnt < n)
            a1 = max(func(now + 1, pos, cnt) + 1, func(now + 1, pos ^ 1, cnt + 1));
        else
            a2 = func(now + 1, pos, cnt) + 1;
        return ref = max(a1, a2);
    }
    else {
        int a1 = 0, a2 = 0;
        if (cnt < n)
            a1 = max(func(now + 1, pos, cnt), func(now + 1, pos ^ 1, cnt + 1) + 1);
        else
            a2 = func(now + 1, pos, cnt);
        return ref = max(a1, a2);
    }
}
 
int main() {
    scanf("%d %d", &t, &n);
    for (i = 1; i <= t; ++i) {
        scanf("%d", &arr[i]);
        arr[i]--;
    }
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(1, 0, 0));
 
    return 0;
}