📝 문제 정보#
🧐 관찰 및 접근#
- 위쪽동네 소가 $N$마리, 아래쪽 소가 $1$마리라고 해보자.
- 그러면 연결 방법은 유일하다. 아래 헛간에 모든 위쪽 헛간을 연결해야한다.
- 아래쪽 소가 $2$마리라고 해보자.
- 위쪽 동네의 소를 $U_1, U_2, \cdots, U_k$를 헛간 $D_1$에, $U_{k+1}, \cdots U_N$을 $D_2$에 연결해야 한다.
- 따라서, 다음과 같은 식을 생각해보자.
- $\text{DP}[i][j]$: 위쪽 동네 소를 $i$마리, 아래쪽 동네 소를 $j$마리를 딱 매칭시켯을때 최솟값
- $\text{DP}[i][j] = min_{k < j}(DP[k][j-1] + \text{Cost}[k+1][i][j])$
- 위와 같은 느낌의 식이 성립할 것 같은데, Cost를 구하는것도, DP식을 구하는것도 쉽지 않아보인다.
- 하 이 식이 뭔가 위 / 아래쪽에 대해 대칭인게 의미심장한데…
- 아 스읍 이게 까다롭네.. 생각해보면, 어떤 간선을 연결했을때, 왼쪽/오른쪽에 남는 개수를 곱한만큼 에 그 경로의 길이를 곱한게 전체에 더해지는데 흠
- 아니근데 약간 그리디하게 안되나? 위랑 아래랑 같은 좌표인게 있으면 이게 무조건 잇는게 이득이 아니라고? 왜지? 경로가 길어질수가 있나?
- 그림을 열심히 그리다보니, 결국 간선은 두가지로 나뉜다.
- Type 1: 반대쪽 정점에 간선이 3개 이상 있고 그 중간에 있어서 해당 간선의 거리에 $N+M-1$이 곱해진다.
- Type 2: 반대쪽 정점의 가장자리 간선이라서, 해당 간선이 $i - j$를 잇는다면 $(i+j-1)(N+M-(i+j-1))$이 곱해진다.
- 그러면 각 $\text{DP}[i][j]$에 대해 마지막 친구에 대해 위에 몇개, 아래 몇개 들어있는지를 관리할 수 있지 않을까? 0개일 수는 없고, 1개면 Type1이 되고, 2개 이상이면 원래 간선을 Type2로 처리하고 Type 1을 붙이는 꼴로 될거같은딩
💻 풀이#
- 코드 (C++):
ll type1(int i, int j){
return dist(i, j) * (N + M - 1);
}
ll type2(int i, int j){
return dist(i, j) * (i + j + 1) * (N + M - i - j - 1);
}
void solve(){
cin >> N >> M >> L;
rep(i, 0, N) cin >> U[i];
rep(i, 0, M) cin >> D[i];
rep(i, 0, N) rep(j, 0, M) rep(k, 0, 2) rep(l, 0, 2) DP[i][j][k][l] = 1e18;
DP[0][0][0][0] = type2(0, 0);
rep(i, 0, N) rep(j, 0, M) rep(k, 0, 2) rep(l, 0, 2){
// 아래 헛간에 새로운 위 헛간 붙이기
ll &cur = DP[i][j][k][l];
if(i+1 < N){
ll &ret = DP[i+1][j][0][1];
if(l == 0) ret = min(ret, cur + type2(i+1, j));
else ret = min(ret, cur - type2(i, j) + type1(i, j) + type2(i+1, j));
}
// 위 헛간에 새로운 아래 헛간 붙이기
if(j+1 < M){
ll &ret = DP[i][j+1][1][0];
if(k == 0) ret = min(ret, cur + type2(i, j+1));
else ret = min(ret, cur - type2(i, j) + type1(i, j) + type2(i, j+1));
}
}
ll ans = 1e18;
rep(k, 0, 2) rep(l, 0, 2) ans = min(ans, DP[N-1][M-1][k][l]);
cout << ans << '\n';
}