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/
