코딩생활

https://jungol.co.kr/problem/4729아이디어그리디 알고리즘이 통합니다. 현재 상태에서 초부피를 가장 크게 증가시킬 수 있는 카드를 사용하는것을 $K$번 반복해주면 됩니다. 증명)현재 A,B,C,D의 값이 순서대로 $A,B,C,D$라고 해봅시다. 그리고 현재 카드중에서 초부피를 가장 크게 증가시킬 수 있는 카드를 $M$이라고 해봅시다. 일반성을 잃지않고, $M$은 A를 $V_M$만큼 증가시킨다고 해봅시다. 만약 이 카드가 쓰이지 않는 최적해가 있다고 가정해봅시다. 그러면 A를 증가시키는 카드는 없음을 알 수 있습니다. A를 증가시키는 카드가 있다면, 그 카드를 $M$으로 교체하여 최적해를 키울 수 있기 때문입니다. 그러므로 사용하는 카드들은 B,C,D를 키우는 카드입니다. 남아있는 ..

PS,CP 2026. 6. 1. 16:00

https://jungol.co.kr/problem/6122아이디어세그먼트 트리를 만들어줄것입니다. 이때 트리의 각 노드가 저장하는 구간의 다음과 같은 값들을 저장해줄 것입니다. $Max$ - 구간 내의 최댓값$Min$ - 구간 내의 최솟값$MaxMin$ - 구간 내의 $l,r (l$MinMax$ - 구간 내의 $l,r (l$MinMaxMin$ - 구간 내의 $a,b,c (a 이때 두 구간을 합치는것은 $O(1)$에 수행할 수 있으므로 이를 세그먼트 트리에 넣어주면 됩니다.아이디어#include #include #define ll long longusing namespace std;struct Range{ ll Max=-1e17,Min=1e17,MaxMin=-1e17,MinMax=-1e17,MinM..

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

https://jungol.co.kr/problem/5346아이디어h1과 h2를 같게 만들기 위한 유일한 방법은 h2와 h3에서 어떠한 수를 빼주는것입니다. 마찬가지로 h3와 h4를 같게 만들기 위한 유일한 방법은 h4와 h5에서 어떠한 수를 빼주는 것입니다. 만약 빼줄 수 없다면, 즉 더해주어야 같게 맞추어진다면 -1을 출력해주면 됩니다. 이를 반복하면 h1과 h2가 같아지고, h3와 h4가 같아지고,... 가 됩니다. 이때 N의 홀짝성에 따라서 풀이가 나누어지게 됩니다. 만약 N이 짝수라면, 먼저 hN-1과 hN이 같은지를 확인해주어야합니다. 만약 다르다면, -1을 출력해주면 됩니다. 만약 같다면, h1과 h2를 세트, h3과 h4를 세트, ... hN-1과 hN을 세트로 놓고 그 세트중 최솟값을 기..

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

https://jungol.co.kr/problem/4188아이디어주어진 수열을 문자열이라고 생각해봅시다. 그리고 접미사배열과 LCP 배열을 만들어줍시다. 그러면 LCP배열 상에서 크기가 K-1인 구간을 잡고 그 구간 내에서의 LCP 값의 최솟값을 L이라 하면, 그 구간에서는 길이가 L인 부분문자열이 K개 존재한다는것을 의미합니다. 그러므로 LCP배열을 잡고 임의의 크기가 K-1인 구간에 대해서 LCP값의 최솟값중 최댓값을 구해주면 됩니다.소스코드#include #include #include #include #define ll long longusing namespace std;ll N;vector GetPi(vector arr){ vector Pi(N); ll idx=0; for..

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

https://codeforces.com/contest/2229/problem/B아이디어어떠한 최적해가 존재하는데, 어떤 인덱스 i에 대해서 ai>bi라고 해봅시다. 이 상황에서 ai와 bi를 swap해도 결괏값이 감소하지 않음을 보일 수 있습니다. 그러므로 항상 a,b중 b에 더 큰 값이, a에 더 작은 값이 들어가는 경우가 최적의 경우임을 알 수 있습니다.소스코드#include #include #define ll long longusing namespace std;ll arr[101010]={0};int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll T; cin>>T; while (T--) { ll N..

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

https://codeforces.com/contest/2229/problem/A아이디어최대 한 칸씩만 움직일 수 있으므로 최댓값과 최솟값이 만나기 위한 최소 이동 횟수를 구해주면 됩니다. 그러므로 (최댓값-최솟값+1)을 2로 나눈 몫을 출력해주면 됩니다.소스코드#include #include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll T,N,i,x,mx,mn; cin>>T; while (T--) { cin>>N; mx=0,mn=2e9; for (i=0;i>x; mx=max(mx,..

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

https://jungol.co.kr/problem/1255아이디어가능한 모든 순서로 배열해봅시다. 하나의 배열이 정해지면 가능한 최소의 직사각형의 크기를 어떻게 구할 수 있을까요? 첫번째 원의 중심의 x좌표를 0이라고 해봅시다. i번째 원의 중심의 x좌표는 max(j번째 원의 중심의 x좌표+(i번째 원과 j번째 원 사이의 x좌표의 차))로 나타낼 수 있습니다. 이때 i번째 원과 j번째 원 사이의 x좌표의 차는 두 원의 반지름을 알고있으므로 피타고라스의 정리를 사용해주면 sqrt(4*(j번째 원의 반지름)*(i번째 원의 반지름))이 됩니다. 마지막에 직사각형의 크기는 max(i번째 원의 x좌표+반지름)-min(i번째 원의 x좌표-반지름)를 해주면 됩니다.소스코드#include #include #inclu..

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

https://jungol.co.kr/problem/3870아이디어모든 간선의 가중치가 다르므로 가중치가 연결되는 순서대로 트리를 만들어줍시다.만약 처음에 1과 2가 연결된다면 새로운 노드 K를 만들어서 1과 2의 공통부모로 만들어줍시다. 그리고 2와 3이 연결된다면 새로운 노드 K+1을 만들어서 K와 3의 공통부모 K+1을 만들어줍시다. 여기서 4와 5가 연결되면 4와 5의 공통부모 K+2, 1과 4가 연결되면 K+1과 K+2의 공통부모 K+3을 만들어줍시다. 그러면 a와 b가 연결되는 최소의 t값은 a와 b의 최소공통조상이 어떤 간선을 연결하였을 때 만들어졌는지를 확인하면 되고, 그때의 연결된 노드의 개수는 그 최소공통조상을 루트로 하는 서브트리에서의 리프노드의 개수를 세어주면 됩니다.소스코드#inc..

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