코딩생활

https://jungol.co.kr/problem/1769?cursor=NTkwLDYsMQ==아이디어현들의 집합을 잡았다고 해봅시다. 여기서 임의의 원소 [l1,r1], [l2,r2]에 대해서 l1 dp[i][j]를 구간 [i,j] 안에 포함되는 현들의 집합에서의 정답값이라고 해봅시다. 만약 [i,j]의 현이 존재한다면, dp[i][j]는 dp[i+1][j-1]+1이 가능합니다. 그렇지 않다면 i이상 j미만의 모든 k에 대하여 dp[i][j]는 dp[i][k]+dp[k+1][j]도 가능하게 됩니다. 이러면 O(N3) DP로 문제를 해결해줄 수 있습니다.소스코드#include #include #define ll long longusing namespace std;ll dp[111][111]={0};boo..

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

https://codeforces.com/contest/2225/problem/B아이디어s[i]==s[i+1]인 i의 개수를 세어봅시다. 만약 그 개수가 0이라면, 항상 가능합니다.만약 그 개수가 1이라면, 앞에서부터 연속된 구간을 선택함으로써 가능하게 됩니다.만약 그 개수가 2라면, s[i]==s[i+1]인 두 인덱스 i를 i1, i2라고 해봅시다. 그러면 구간 [i1+1,i2]에 대해서 연산을 적절히 수행해주면 항상 가능합니다.만약 그 개수가 3이상이라면, 항상 불가능합니다.아이디어#include #include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ..

PS,CP 2026. 5. 17. 16:00

https://codeforces.com/contest/2225/problem/A아이디어y=kx라고 해봅시다. 만약 k가 3이상이라면 z=(k-1)x를 함으로써 조건을 만족시킬 수 있습니다. 만약 k가 2라면 z를 찾을 수 없습니다. 그러므로 y/x의 값이 2이면 NO를, 아니면 YES를 출력해주면 됩니다.소스코드#include #include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll T,x,y; cin>>T; while (T--) { cin>>x>>y; cout

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

https://jungol.co.kr/problem/8565?cursor=MjcsMSwxMw==아이디어idx[x]를 x중에서 먼저 나온것의 위치라고 생각합시다. 앞에서부터 보면서 idx[x]가 0이면 idx[x]에 현재 인덱스를 넣어주고, 아니면 (현재 인덱스-idx[x]-1)의 최댓값을 구해주면 됩니다.소스코드#include #include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll N,i,x,idx[2020]={0},res=0; cin>>N; for (i=1;i>x; if (idx[x]==0) idx[x]=i; e..

PS,CP 2026. 5. 16. 16:00

https://jungol.co.kr/problem/5768아이디어모든 인덱스 i에 대해서 idx[i]를 (i와 같은 수가 있고 i보다 오른쪽에 있는 가장 작은 인덱스)라고 정의합시다. 그러면 모든 i에 대해서 구간 [i+1,idx[i]-1]에 존재하는 서로다른 수의 개수를 모두 더해주면 됩니다. 이는 mo's로 해결해줄 수 있습니다.소스코드#include #include #include #include #define ll long longusing namespace std;ll sqrtN;bool cmp(pair A,pair B){ if (A.first/sqrtN!=B.first/sqrtN) return A.first>N; sqrtN=sqrt(N); vector > Query; ..

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

https://jungol.co.kr/problem/11187아이디어어떤 간선 E가 MST에 들어가기 위해서는 E보다 가중치가 낮은 간선들을 다 이었을 때 E의 양 끝점을 잇는 경로에서 최소 몇개의 간선을 끊어야하는지로 정의할 수 있습니다. 이는 최대유량-최소컷 정리에 의해서 E의 양 끝점을 시작점과 도착점으로 하는 최대 유량을 구해주면 됩니다.소스코드#include #include #include #include #include #define ll long longusing namespace std;vector Graph[111];ll MaxFlow(ll Start,ll End){ ll res=0; ll Flow[111][111]={0},Cap[111][111]={0}; for (ll..

PS,CP 2026. 5. 15. 16:00

https://jungol.co.kr/problem/3621아이디어모노톤 덱을 이용해줍시다.dp[i]를 i번째까지의 소들을 가지고 얻을 수 있는 최댓값으로 정의합시다. 이 경우는 두가지로 나눌 수 있습니다. - i번째 소를 선택하지 않는 경우 -> dp[i-1]의 값과 동일- i번째 소를 선택하는 경우 -> i-K이상의 j를 선택하여 (dp[j-1]-sum[j])+sum[i]중 최댓값을 저장함 두번째 경우는 j에 의존하는 부분과 i에 의존하는 부분으로 나눌 수 있기 때문에 모노톤 덱을 이용해서 (dp[j-1]-sum[j])의 최댓값을 저장해주면 됩니다. 이 덱은 앞에서 뒤로 갈수록 j값은 증가, dp[j-1]-sum[j]값은 감소하며, 새로운 값을 넣을때에는 뒤에 넣는데, 뒤에 dp[j-1]-sum[j]..

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

https://jungol.co.kr/problem/12491?cursor=MjcsMCwz아이디어두 포인터를 이용해서 어떤 인덱스를 기준으로 거리가 K1이하인 점들의 범위를 구해줍시다. 그리고 그 안에 있는 모든 학생의 학교별 인원수를 체크해줍니다. 이를 두개의 포인터를 더 사용해서 거리가 K2이하인 점들까지 고려해줍니다. 그러면 각 사람마다 O(1)에 개수를 세어줄 수 있습니다.소스코드#include #include #include #include #define ll long longusing namespace std;ll Count1[505050]={0},Count2[505050]={0};ll Ans[505050]={0};int main(){ ios_base::sync_with_stdio(fal..

PS,CP 2026. 5. 14. 16:00