백준 14462번 소가 길을 건너간 이유 8 - C++(cpp) 풀이

---

 

1. 왼쪽 목초지의 i번째 소를 연결하는 경우, 오른쪽 소 중 가장 앞쪽에 있는 소와 연결하는 것이 최적이다.
2. dp(l, r) = left_cows[l...]과 right_cows[r...] 사이에 놓을 수 있는 횡단보도의 최대 개수
3. dp(l, r) = max(왼쪽의 l번째 소는 연결하지 않는 경우, 왼쪽의 l번째 소와 오른쪽의 i번째 소와 연결하는 경우)

 

1. 왼쪽 목초지의 i번째 소를 연결하는 경우, 오른쪽 소 중 가장 앞쪽에 있는 소와 연결하는 것이 최적이다. 

 왼쪽 목초지의 소를 기준으로 차례로 연결한다고 하면, 횡단보도가 겹치지 않기 위해서는 연결시키는 오른쪽 목초지의 소도 오름차순이어야 한다. 즉, 더 나중에 매칭하는 오른쪽 소의 번호가 작아지면 안 된다. 이전 매칭에서 최대한 앞쪽의 소와 매칭을 해두어야 다음 매칭에서 매칭 후보군이 많아지므로, 최대한 앞쪽부터 그리디하게 매칭 한다면 최대로 매칭 할 수 있음을 알 수 있다.

 

2. dp(l, r) = left_cows[l...]과 right_cows[r...] 사이에 놓을 수 있는 횡단보도의 최대 개수

 왼쪽 목초지의 소를 차례로 하나씩 연결한다고 하자. 왼쪽의 i번째 소를 오른쪽의 j번째 소와 매칭 했다고 하면, 이제 왼쪽 목초지에는 i+1번째 소 ~ 마지막 소까지 남아있고, 오른쪽 목초지에는 j+1번째 소~마지막 소가 남아있는 재귀적인 상황이 된다. (j번보다 앞에 있는 오른쪽 소와 매칭 하면 횡단보도가 겹치게 되므로 이제 j+1번째 이후 소들과만 매칭 할 수 있다.) 따라서 DP로 해결할 수 있다.

 

3. dp(l, r) = max(왼쪽의 l번째 소는 연결하지 않는 경우, 왼쪽의 l번째 소와 오른쪽의 i번째 소와 연결하는 경우)

 왼쪽의 l번째 소에 대해 매칭 하는 경우와 안 하는 경우 중 더 많은 횡단보도를 설치할 수 있는 경우를 선택하면 된다. 연결하지 않는 경우는 dp(l+1, r)이 되고, 연결하는 경우에는 최대한 앞쪽에 있는 소 f와 매칭해야 하므로 1 + dp(l+1, f+1)이 된다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

const int MAX = 1000;

int N;
int left_cows[MAX], right_cows[MAX], cache[MAX][MAX];

// dp(l, r) : left_cows[l...]과 right_cows[r...]사이에 놓을 수 있는 횡단보도의 최대 갯수
int dp(int l, int r) {
    if (l == N || r == N) return 0;
    
    int& ret = cache[l][r];
    if (ret != -1) return ret;
    
    ret = dp(l+1, r);
    for (int i=r; i<N; i++) {
        if (abs(left_cows[l] - right_cows[i]) > 4) continue;
        ret = max(ret, 1 + dp(l+1, i+1));
        break;
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> N;
    for (int i=0; i<N; i++) cin >> left_cows[i];
    for (int i=0; i<N; i++) cin >> right_cows[i];
    
    cout << dp(0, 0);
    
    return 0;
}