494 words
2 minutes
[BOJ] Cowties
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
1s | 1024MB | (3 ≤ N ≤ 100) | Dynamic Programming |
그냥 대놓고 dp 문제 준거여서 그대로 읽고 그대로 풀면 되었씁니다. 약간 조심할거는…
”처음 시작했던 점이랑 이어져야한다는 것” 정도 겠네요.
정답 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <math.h>
using namespace std;
using ll = unsigned long long;
using ld = long double;
//ll MOD = 1'000'000'007;
//ll MOD = 1.8446744074E19;
int N;
// 그냥 dp로 풀면 될걱 ㅏㅌ긴한ㄷ
//ld dp[101][
// 그니까 i번째 cow를 보고 잇느 상황에서.. j번째 위치로 선택했ㅇ르 때 최소값을 얻어가면 되는거자너
// dp[i][j]를 i번째 cow의 j번째 position으로 확정할 때 그 전까지의 loop length 최솟값으로 정하자. // 이거 길이가 분수가 나오니까 double 로 하고 마지막에만 100 곱하기로
// 이게 그냥 간단히 끝나는건 아니였구만..
ld dp[101][101];
vector<pair<int, int>> cows[101];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ld a = LLONG_MAX;
cin >> N;
for(int i = 0; i < N; i++){
int tmp;
cin >> tmp;
for(int j = 0; j < tmp; j++){
int y, x;
cin >> y >> x;
cows[i].push_back({y, x});
}
}
ld result = LLONG_MAX;
for(int first = 0; first < cows[0].size(); first++){
for(int i = 1; i < N; i++){
for(int j = 0; j < cows[i].size(); j++){
dp[i][j] = LLONG_MAX;
if(i == 1){
auto [cy, cx] = cows[i][j];
auto [py, px] = cows[0][first];
ld distance = sqrtl((cy - py) * (cy - py) + (cx - px) * (cx - px));
dp[i][j] = distance;
}
}
}
for(int idx = 2; idx < N; idx++){
for(int i = 0; i < cows[idx].size(); i++){
for(int j = 0; j < cows[idx-1].size(); j++){
ld pre_cost = dp[idx-1][j];
auto [cy, cx] = cows[idx][i];
auto [py, px] = cows[idx-1][j];
ld distance = sqrtl((cy - py) * (cy - py) + (cx - px) * (cx - px));
dp[idx][i] = min(dp[idx][i], pre_cost + distance);
}
}
}
for(int i = 0; i < cows[N-1].size(); i++){
ld current = dp[N-1][i];
auto [cy, cx] = cows[N-1][i];
auto [py, px] = cows[0][first];
ld distance = sqrtl((cy - py) * (cy - py) + (cx - px) * (cx - px));
result = min(result, current + distance);
}
}
cout << (ll)(result * 100);
return 0;
}
[BOJ] Cowties
https://compy07.github.io/Blog/posts/boj/27061/