[ BOJ 백준 16437번 - 양 구출 작전 ] 해설 및 코드

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

 

 

목적

N개의 섬들이 트리의 형태로 되어있고, 양이 있는 섬에서 구명보트가 있는 1번 섬까지 양을 몇마리나 살려보낼 수 있는지 구하자.

 

접근법

1. 경로를 따라 양이 이동할 때, 섬을 탐색하는데 경로의 수를 줄이는 것이 문제의 해결법이다.

 

2. 어떠한 섬에 양을 먹어야하는 늑대가 더이상 없는 경우, 그 섬을 탐색에서 제외시켜야 한다. 따라서 양이 최대로 이동한 섬의 번호를 제귀적으로 반환하여 경로를 갱신하자.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;i++)
#define LEN 123457
using namespace std;
 
int n,route[LEN],wolves[LEN],sheep[LEN]{};
long long ans=0;
 
int move(int cnt,int i){
    if(i==1){
        ans+=cnt;
        return 1;
    }
    if(cnt<wolves[i]){
        wolves[i]-=cnt;
        return i;
    }else{
        cnt-=wolves[i];
        wolves[i]=0;
        return route[i]=move(cnt,route[i]);
    }
}
 
int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    
    cin>>n;
    f(i,2,n){
        char t;int a,p;cin>>t>>a>>p;
        if(t=='S') sheep[i]=a;
        else wolves[i]=a;
        route[i]=p;
    }
    
    f(i,1,n)if(sheep[i])move(sheep[i],route[i]);
    cout<<ans;
    return 0;
}
 

 

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

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