코딩생활

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

https://jungol.co.kr/problem/1209아이디어단절선을 기준으로 생각해봅시다. 단절점을 지나지 않고 연결된 노드들을 하나의 집합으로 생각해봅시다. 그러면 그 집합들은 단절점으로 이어져있고, 그 그래프는 트리입니다. 그러므로 트리에서 다리가 하나 끊겼을 때 항상 모든 점이 연결되도록 다리를 놓는 경우를 생각해볼 수 있습니다. 정답부터 말하자면 (리프노드의 개수)/2의 올림값입니다. 이를 편의상 T라고 합시다.증명)정답값이 T이상임을 증명해봅시다. 만약 다리가 T보다 작다면, 다리를 다 설치하였을 때 최소 한개의 리프노드는 그 다리에 연결되어있지 못합니다. 그러면 그 리프노드는 어떤 다리를 끊었을 때 전체 그래프에서 떨어져나올 수 있으므로, 다리를 T보다 적은 개수로 설치할 수는 없습니다..

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

https://jungol.co.kr/problem/1554아이디어2차원 세그먼트 트리를 구현해주면 됩니다. 하지만 이 문제에서는 메모리제한이 작기 때문에 tree[약 2000][약 2000]을 선언해야하며 자료형은 int를 사용해야합니다.소스코드#include #define ll intusing namespace std;ll tree[2222][2222]={0};void UpdateSmall(ll row,ll s,ll e,ll node,ll idx,ll num){ if (idx>type>>N; while (true) { cin>>type; if (type==1) { cin>>a>>b>>c; Update(0,N,..

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

https://jungol.co.kr/problem/2504아이디어모든 컴포넌트에 대하여 그 컴포넌트가 이분그래프인지 확인하고, 이분그래프일때 두 종류의 정점으로 나누고 정점의 개수의 차이를 구하는 모든 과정은 O(N)에 처리가 가능합니다. 만약 모든 컴포넌트가 이분그래프라면, 각 컴포넌트마다 개수의 차이가 생길 것입니다. 이러한 컴포넌트가 K개 존재한다고 해봅시다. dp[i][j]를 i번째 컴포넌트까지 봤을 때 두 종류의 정점의 개수의 차이가 j인것이 가능한가?의 여부로 정의합시다. 이 DP테이블은 O(N2)에 구할 수 있고, 문제를 시간내에 해결할 수 있습니다. 물론 DP테이블이 크므로 두개의 dp[j]를 돌려가면서 사용해야합니다.소스코드#include #include #include #define ..

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

https://jungol.co.kr/problem/8607아이디어s와 c가 주어지면 구간 (c,s]에 표시를 해줍시다. 그리고 어떠한 점 x에 대하여 x에 표시된 개수를 세어줄것입니다. 모든 x에 대하여 표시된 값의 개수의 최댓값이 정답이 됩니다. 증명) 표시된 값의 개수의 최댓값을 P_mx라고 합시다. 정답값이 P_mx이상임은 자명합니다. 어떠한 x에 대하여 표시된 값의 개수가 P_mx라는것인데, 그 표시된 P_mx개의 구간은 서로를 포함할 수 없기 때문입니다. 그러면 정답값이 P_mx이하임은 어떻게 증명할까요?모든 구간을 c가 증가하는 순서대로, c가 같다면 s가 증가하는 순서대로 정렬해줍시다. 그리고 앞에서부터 구간을 하나씩 넣어줄것입니다. 첫번째 구간은 대표구간1이 됩니다. 만약 i번째 구간을 ..

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

https://jungol.co.kr/problem/9657아이디어미리 모든 쿼리들을 입력받아서 가능한 키 값들을 값 압축을 해주어서 1부터 20만까지의 수로 변환해줍시다. 그리고 다시 쿼리들을 앞에서부터 보면서 키가 a인 학생이 x명 들어오면 arr[a]에 x를 더하는 것을 반복해주면 됩니다. 이를 세그먼트 트리에 넣어주면 여기서 임의의 k에 대해 k번째로 작은 학생의 키를 O(log 200000)에 알아낼 수 있습니다. 그러므로 쿼리들을 진행해가면서 그때까지의 총 학생수를 sum이라고 하고, sum이 짝수라면 sum/2번째와 sum/2+1번째 학생중 더 작은 키를, sum이 홀수라면 (sum+1)/2번째 학생의 키를 출력해주면 됩니다.소스코드#include #include #include #defin..

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

https://jungol.co.kr/problem/2842아이디어하나씩 넣으면서 now를 지금까지 넣은 문자들의 맨 뒤에 최대 now개를 고르면 원하는 target 문자열이 된다. 라고 정의합시다. 만약 now가 target문자열의 길이와 같아지면, 제거할 수 있는 것입니다. 이때 now가 증가하다가 원하는 문자가 나오지 않을 때가 있는데 그러면 target의 pi 배열을 미리 만들어서 now값으로 가능한 값을 빠르게 감소시켜주면 됩니다.소스코드#include #include #include #include #include #define ll long longusing namespace std;vector GetPi(string s){ ll N=s.length(),idx=0; vector ..

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