코딩생활

https://codeforces.com/contest/2224/problem/A아이디어뒤에서부터 보면서 a[i]에 a[i+1]을 더하는것이 이득인 경우만 a[i+1]을 더해주는것을 반복해주면 됩니다.소스코드#include #define ll long longusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll T,N,i,arr[202020]={0}; cin>>T; while (T--) { cin>>N; for (i=1;i>arr[i]; } arr[N+1]=0; ll cnt=0; for (i=N;i>=1;i-..

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

https://codeforces.com/contest/2223/problem/A아이디어만약 a[i]와 b[i]가 같다면, 고려하지 않아도 됩니다. 만약 a[i]와 b[i]가 다르다면 a와 b에 번갈아가면서 '('와 ')'를 나누어줍니댜. 즉, 첫번재에는 a[i]에 '('를, b[i]에 ')'를 주고, 두번째에는 a[i]에 ')', b[i]게 '('를 주고, 세번째에는 첫번째와 동일하게 주고...를 반복하면 됩니다.소스코드#include #include #define ll long longusing namespace std;bool Able(string s){ ll cnt=0; for (char c:s) { if (c=='(') cnt++; else cnt--; ..

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

https://jungol.co.kr/problem/2543?cursor=MjAsMSwy아이디어solve(x,y,Sz,a,b)를 왼쪽 위 점의 좌표가 (x,y)이고 한 변의 길이가 Sz인 정사각형에서 (a,b)의 위치를 제외하고 타일을 배치하는 함수라고 해봅시다. 이는 다음과같이 해결할 수 있습니다. 1. 만약 Sz가 2라면, (a,b)가 (x,y)인지, (x+1,y)인지, (x,y+1)인지, (x+1,y+1)인지에 따라서 타일의 모양이 달라집니다.2. 만약 Sz가 2가 아니라면, 주어진 정사각형을 4등분합니다. 그리고 x2=x+Sz/2,y2=y+Sz/2라고 정의합시다. 그러면 (a,b)의 위치가 4개의 정사각형중 하나로 정해집니다. (a,b)가 포함된 정사각형은 그냥 solve를 그대로 해주면 됩니다...

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

https://jungol.co.kr/problem/8679아이디어행은 최대 4000개입니다. 그러므로 각 행마다 그 행에서 가장 늦게 번식되는 위치를 찾아주면 됩니다. 각 행마다 가장 먼저 번식되는 위치는 모든 세균의 열이라고 할 수 있습니다. 그러므로 그 열의 위치에 번식되는 시각을 표시해줍시다. 그런데 만약 서로 d만큼 차이나는 두 열에서의 번식 시각이 d보다 크게 차이가 난다면 더 큰쪽을 작은쪽+d로 맞추어주면 됩니다. 그러면 O(K)에 가장 늦게 번식되는 위치를 찾아줄 수 있습니다. 이것을 각 행마다 시행해주면 O(NK)에 문제를 해결할 수 있습니다.소스코드#include #include #include #include #define ll long longusing namespace std;in..

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

https://jungol.co.kr/problem/12222?cursor=NTA4LDEsNw==아이디어dp[i][j][k][l]을 1번부터 i번째까지 칸까지 봤을 때 햄버거 가게를 j개, 음료수 가게를 k개, 기념품 가게를 l개 골랐을 때의 최대로 만족시킬 수 있는 공룡의 마릿수라고 정의합시다. 그리고 누적합을 통해서 어떠한 구간에 있는 특정 수의 개수를 O(1)에 구해줍시다. 그러면 dp테이블을 채워줄 수 있습니다. 그리고 dp[N]값을 보면서 최대한 많은 공룡을 만족시키고, 그러한 경우의 수가 여러 개 있다면, 매장을 최소한으로 사용하는 경우를 구해주어야합니다. dp[N]의 값을 보면서 그러한 값을 찾고 역추적을 통해 어느 위치에 가게를 놓을지 정해주면 됩니다.소스코드#include #include..

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

https://jungol.co.kr/problem/12203?cursor=NTA4LDEsNg==아이디어dp[i][j]를 i번째칸에 도달하기 직전이고 그때까지의 j개의 아이템을 먹었을때의 걸리는 최소 시간이라고 정의합시다. 그러면 dp[i][j]와 i번째 칸에 아이템이 있는지의 여부를 바탕으로 dp테이블을 채워줄 수 있습니다. 만약 도착점이 N을 넘어선다면, 그때까지의 시간을 기록하여 마지막에 최솟값을 구해주면 됩니다.소스코드#include #include #define ll long longusing namespace std;ll dp[5050][5050]={0};int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll N,i,j; ..

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

https://jungol.co.kr/problem/1994?cursor=NTA4LDAsOA==아이디어멀티소스 다익스트라를 이용해서 모든 노드에 대해 동아리로부터 떨어진 거리를 구해줍니다. 만약 하나의 시작점-도착점 쿼리가 있다면, 동아리로부터의 거리가 먼 노드부터 하나씩 추가하면서 시작점과 도착점이 연결되는 순간을 유니온 파인드를 이용해 구해주면 됩니다. 하지만 이러한 쿼리가 여러개가 있다면, PBS를 사용해야합니다. PBS는 병렬 이분 탐색으로, 어떤 쿼리에 대해서 동아리로부터의 거리가 가장 먼 K개의 노드만을 가지고 이동할 수 있는가? 라는 질문으로 매개변수탐색을 해주면 됩니다. 그러면 O(M log N)에 문제를 해결해줄 수 있습니다.소스코드#include #include #include #inc..

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

https://jungol.co.kr/problem/3900?cursor=NTA4LDAsNw==아이디어세그먼트 트리를 만들어서 특정 구간 내의 모든 고깔을 방문했을 때의 이동거리와 한개를 제외하고 방문했을 때의 최소 이동거리를 저장합시다. 이때 인접한 두 구간을 합칠 때 모든 고깔을 방문하는 경우는 그냥 (왼쪽 구간의 모든 고깔 방문)+(두 구간 사이 점의 거리)+(오른쪽 구간의 모든 고깔 방문)을 해주면 되며, 하나를 제외하고 방문하는 경우는 추가로 왼쪽 구간의 맨 오른쪽 고깔을 지나지 않는 경우와 오른쪽 구간의 맨 왼쪽 고깔을 지나지 않는 경우를 고려해주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;struc..

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