코딩생활

https://jungol.co.kr/problem/1720?cursor=MTMsMiwx아이디어모든 지점을 높이순으로 정렬해줍시다. 그리고 모든 연속된 구간에 대해서 그만큼의 도시를 선택했을때의 최단경로를 구해줍시다. 이를 반복해주면 됩니다.소스코드#include #include #include #include #define ll long longusing namespace std;vector > Graph[111];bool Use[111]={0};ll dij(ll Start,ll End){ if (!Use[Start] || !Use[End]) return 1e18; priority_queue , vector >, greater > pq; ll dp[111]={0}; for (l..

PS,CP 2026. 5. 1. 21:39

https://jungol.co.kr/problem/1151?cursor=MTIsNiw0아이디어CCW를 이용해서 볼록 껍질을 구해주면 됩니다. 그리고 신발끈 공식을 이용해서 그 넓이를 구해주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;ll CCW(pair A,pair B,pair C){ ll ax=A.first,ay=A.second,bx=B.first,by=B.second,cx=C.first,cy=C.second; ll ccw=ax*(by-cy)+bx*(cy-ay)+cx*(ay-by); if (ccw0) return 1;}bool ycmp(pair A,pair B){ if (A.se..

PS,CP 2026. 5. 1. 09:00

https://jungol.co.kr/problem/3599?cursor=MTIsMiwz아이디어LCA를 구현하여주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;vector Graph[303030];ll dpt[303030]={0},par[303030][22]={0};void DFS(ll node,ll before){ dpt[node]=dpt[before]+1; par[node][0]=before; for (ll i=1;i=0;i--) { if (dpt[par[a][i]]>=dpt[b]) a=par[a][i]; } if (a==b) return a; ..

PS,CP 2026. 4. 30. 16:00

https://jungol.co.kr/problem/8336?cursor=MTIsMiwx 연봉 계산하기 · Platinum IIIPlatinum III · 19 solved users · 34 submissionsjungol.co.kr아이디어오일러 투어 테크닉과 느리게 갱신되는 세그먼트 트리를 이용해주면 문제를 해결할 수 있습니다.소스코드#include #include #include #define ll long longusing namespace std;ll tree[2020202]={0},lazy[2020202]={0};void pp(ll s,ll e,ll node){ tree[node]+=lazy[node]; if (s!=e) { lazy[node*2]+=lazy[nod..

PS,CP 2026. 4. 30. 09:00

https://jungol.co.kr/problem/3005?cursor=MTIsNiwz아이디어신발끈 공식을 이용해주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;double Area(vector > v){ ll N=v.size(); v.push_back(v.front()); ll res=0; for (ll i=0;i > v; cin>>N; for (i=0;i>a>>b; v.push_back({a,b}); } cout

PS,CP 2026. 4. 29. 16:00

https://koistudy.net/prob_page?NO=4319&resubmit_sID=5592895아이디어일단 기본 아이디어는 (랜덤 경로 만든 후 2-opt 5번 돌리기)*적당히 많이 한 후 2-opt로 최적화 이다. 이 방법으로 1090점까지 받았다.소스코드#include #include #include #include #include #include #include #define ll long longusing namespace std;using namespace chrono;vector > Dots;double Dis(array A,array B){ double dx=A[0]-B[0],dy=A[1]-B[1],dz=A[2]-B[2]; return sqrt(dx*dx+dy*dy..

PS,CP 2026. 4. 29. 09:00

https://jungol.co.kr/problem/4826?cursor=MTEsMSwx아이디어모든 (x,y)는 (|x|,|y|)로 치환할 수 있습니다. 그리고 x좌표 순으로 정렬을 해줍니다. 그리고 점들의 구간을 나누어서 그 구간 내의 점들은 같은 직사각형을 공유하도록 만들면 됩니다. 그러면 문제를 시간내에 해결할 수 있게 됩니다.소스코드#include #include #include #define ll long longusing namespace std;ll dp[5050]={0};int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll N,i,x,y; vector > v; v.push_back({0,0}); cin..

PS,CP 2026. 4. 28. 16:00

https://jungol.co.kr/problem/4822?cursor=MTEsMCw2아이디어몇개의 열쇠고리를 골랐을 때 그 열쇠고리들을 다 설치할 수 있을 필요충분조건은 모든 열쇠고리에 대해서 a-1값의 합이 -1이상이라는 것입니다. 그러므로 dp[i]를 지금까지의 a-1의 합이 i일때의 최대 만족도라고 정의하면 문제를 해결할 수 있습니다. 이때 dp가 음수가 될 수 있으므로 인덱스에 N씩 더해서 저장해주고, N초과의 값은 그냥 N으로 처리해도 되므로 dp[0]부터 dp[2N]까지만 사용해주면 됩니다.소스코드#include #define ll long longusing namespace std;ll dp[4040]={0};int main(){ ios_base::sync_with_stdio(fal..

PS,CP 2026. 4. 28. 09:00