Compy's Blog
494 words
2 minutes
[BOJ] Cowties
2025-10-06

Cowties

TimeLimitMemoryLimitConditionTAG
1s1024MB(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/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-10-06