[ BOJ 백준 2585번 - 경비행기 ] 해설 및 코드

https://www.acmicpc.net/problem/2585

 

 

목적

다음 그림과 같이 S(=출발지: {0,0}), T(=도착지: {10000,10000}), 그리고 N개의 경유지가 있는데, M번을 경유하여 S에서 T로 가기위해 필요한 연료통의 최소 용량을 구하자.

접근법

1. 연료통의 용량을 1에서 S에서 T까지 가는데 필요한 양까지를 범위로 하는 이분탐색 알고리즘을 적용한다. 

2. 제곱근을 구하는 오버헤드가 어느정도 존재하므로, 이 연산은 생략하고 진행한다.

 

#include<iostream>
#include<cstring>
#define DIST(a,b,c,d) ((a-c)*(a-c)+(b-d)*(b-d))
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
int a[1001][2]={{0,0}},n,k,lim,z[1001];
 
bool possible(int i,int cnt){
    if(cnt<1)return false;
    z[i]=1;
    f(j,1,n)if((!z[j]&&DIST(a[i][0],a[i][1],a[j][0],a[j][1])<=lim)&&
               (DIST(a[j][0],a[j][1],10000,10000)<=lim||possible(j,cnt-1)))return true;
    return false;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    
    f(i,1,n)cin>>a[i][0]>>a[i][1];
    
    int l=1,r=15000;
    while(l<=r){
        memset(z,0,sizeof(z));
        int mid=(l+r)/2;
        lim=mid*mid*100;
        if(possible(0, k))r=mid-1;
        else l=mid+1;
    }
    cout<<l;
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.