PS23 [백준] 10159 - 저울 (c++) https://www.acmicpc.net/problem/10159한국정보올림피아드시․도지역본선 > 지역본선 2014 > 고등부 2번한국정보올림피아드시․도지역본선 > 지역본선 2014 > 중등부 3번한국정보올림피아드시․도지역본선 > 지역본선 2014 > 초등부 4번문제 요약N개의 물건 사이에 M개의 대소관계가 주어진다. (1~N) i물건과 대소관계를 알 수 없는 물건의 개수를 출력해라. 풀이 (N^3)플로이드각 정점에 갈 수 있는 정점수와 올 수 있는 정점수를 구해야 한다. 정방향과 역방향으로 위상정렬dp를 두 번 돌려서 하는 방법이 바로 떠올랐는데 플로이드 한 번으로 모두 구할 수 있단 걸 알고 플로이드로 구현했다.#include using namespace std;#define ll long long.. 2024. 11. 29. [백준] 3267 - TWO (c++) https://www.acmicpc.net/problem/3267 Croatian Highschool Competitions in Informatics > 2002 > National Competition #2 - Seniors 3번 문제 요약청소부 두명이 트리를 청소하려고 한다. 주어진 트리에서 모든 간선을 한 번 이상 거치면 청소를 마쳤다고 한다. 트리와 청소부의 시작 위치가 주어질 때 청소부가 청소를 마치는데 걸리는 최소 시간을 구해라. 풀이 (M+N)DFS한 번만 거치는 간선이 있고 왕복을 해야 하는 간선이 있을 것이다. 한 번만 거치는 길이가 클 수록 좋기 때문에 트리의 지름을 구해준다. 지름에 포함되지 않는 간선은 모두 왕복해야 하기 때문에 답은 ((가중치 총합-지름)*2+지름)이 된다. 시작.. 2024. 11. 20. [백준] 2317 - 결혼식 (c++) https://www.acmicpc.net/problem/2317 문제 요약N개의 수가 주어진다. K개의 수는 순서를 바꿀수 없고 나머진 바꿀 수 있을 때, 인접한 앞뒤 수의 차이를 모두 더한 값의 최솟값을 구해라. 풀이 (N)그리디순서를 바꿀 수 없는 수들 사이에 바꿀 수 있는 수를 최소가 되게 잘 끼워 넣으면 된다. [l,r] 구간에 속하는 수들에 대해 비용은 r-l이기 때문에 최솟값과 최댓값만 신경쓰면 된다. 순서를 바꿀 수 있는 수들과 바꿀 수 없는 수들의 최솟값과 최댓값을 각각 hmn,hmx,lmn,lmx라고 하자. hmnlmx일 때 수를 가운데 끼워 넣거나 양 끝에 넣는 경우 중 가장 차이가 적은 것을 고르면 된다. #include using namespace std;#define ll lon.. 2024. 11. 19. [백준] 2185 - 직사각형의 합집합 (c++) https://www.acmicpc.net/problem/2185IOI 1998 > Day 2 4번 문제 요약직사각형 여러개가 입력으로 주어진다. 직사각형의 합집합의 둘레를 구해라 풀이 (Nlog(max_coord))스위핑세그먼트 트리세그먼트 트리를 안 쓰고 N*(max_coord) 풀이도 충분히 돌아간다. 하지만 연습삼아 세그트리를 써서 시간복잡도가 좋은 풀이를 내봤다. x축 y축 나눠서 스위핑을 한다고 생각해보자 둘레가 갱신되는 건 길이에 변화가 생기는 순간이란 관찰을 할 수 있다. 구간안에 전체 길이를 세그로 구하면 길이가 달라질 때, 달라진 만큼 답에 더해주면 된다. 중복을 제외하고 길이를 구하는 테크닉은 이 블로그에 자세히 나와있다.https://ps.mjstudio.net/0-1-segment.. 2024. 11. 19. [백준] 1854 - K번째 최단경로 (c++) https://www.acmicpc.net/problem/1854 문제 요약가중치가 있는 그래프가 방향 그래프가 주어진다. 1에서 i(1~N)로 가는 K번째 최단경로의 길이를 출력해라. 풀이 (K(M*logN))다익스트라정점에 K번째로 갱신되는 경로가 K번째 최단경로가 된다.#include using namespace std;#define ll long longint main() { cin.tie(0)->sync_with_stdio(0); int n,m,k;cin>>n>>m>>k; ll cnt[n+1]{},dis[n+1]{}; fill(dis,dis+n+1,1e18); vector> adj[n+1]; for(int i=0,u,v,c;i>u>>v>>c,adj[u].push_.. 2024. 11. 18. [백준] 3233 - BRODOVI (c++) https://www.acmicpc.net/problem/3233Croatian Highschool Competitions in Informatics > 2003 > Regional Competition - Seniors 4번 문제 요약N크기의 강에 칸 마다 물고기에 개수가 주어진다. M개의 닻을 내릴 위치와 배의 크기가 주어질 때 배를 닻에서 벗어나지 않게 옮겨서 잡을 수 있는 물고기의 최댓값을 구해라. 풀이 (MlogM)스위핑DP누적합닻을 스위핑하면서 1차원 DP배열을 업데이트 해주면 된다. 배가 서로 겹칠 수 없기 때문에 현재 배가 전,후 닻까지 가지 못하게 하고 범위안에서 누적합으로 잡을 수 있는 물고기를 구해 업데이트 해준다. 배가 가지 못하는 곳도 생기기 때문에 갱신 했던 마지막 위치 부터 현.. 2024. 10. 31. 이전 1 2 3 4 다음