백준 2842 집배원 한상덕 혼내주기
아이디어를 못 떠올려서 sds 알고리즘 특강 강사님의 아이디어를 보고 구현했다. 투 포인터로 모든 집을 방문할 수 있는 구간의 피로도 최솟값을 구하면 된다. 고도는 1 ~ 1000000의 수이지만 총 지역이 최대 2500개 이므로 해당 고도 내에서만 투 포인터로 찾으면 된다. 시간복잡도는 bfs가 O(n2)이고 투 포인터가 O(n2)으로 총 O(n4)가 된다. 이런 문제는 몇번만 더 풀어보면 점점 아이디어가 보일 것 같다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int ..
혼내주기
2021. 7. 22. 10:48