너와 나의 스토리

문제: https://www.acmicpc.net/problem/2468 문제 풀이 1 - BFS: 입력 중 가장 높은 지역의 높이를 maxH라고 하자. 모든 높이에 대해 다음 연산을 수행한다. 현재 높이를 h라고 할 때, h보다 큰 값들을 bfs를 통해 덩어리의 개수를 구한다. 이때 visit 변수를 사용하게 되는데 높이마다 새롭게 visit 변수를 표시해야 한다. 이를 memset을 이용하여 초기화해도 되지만, 이렇게 하면 시간을 더 소비하게 된다. 그래서 나는 visit을 true, false로 표시하는 것 대신, 현재 높이로 방문한 사실을 기록하여 visit 변수 초기화하지 않아도 되도록 하였다. 시간: 668ms 소스 코드: 더보기 #include #include #include #include..

문제: https://www.acmicpc.net/problem/15789 문제 풀이: 동맹 왕국들 입력 받을 때마다 merge해주고 cnt[root]=(node 개수) 업데이트 해주기 각 동맹 왕국들의 루트와 동맹 왕국들의 수를 priority_queue에 저장 동맹 기회만큼 merge하는데 자기 자신의 그룹이거나 한솔 왕국 그룹과는 동맹 맺지 않고 그냥 pop 소스 코드: typedef pair P; int n, m,p[100001],cnt[100001]; bool visit[100001]; vector v; priority_queue res; int find(int x) { if (p[x] < 0) return x; return p[x] = find(p[x]); } bool merge(int a, ..

문제: https://www.acmicpc.net/problem/10775 문제 설명: G개의 게이트가 있고, P개의 비행기가 순서대로 도착할 예정이다. 도착한 비행기에게 주어진 값 gi이하의 게이트에만 비행기를 도킹할 수 있고, 이미 다른 비행기가 도킹한 곳에 도킹할 수 없다. 그리고 "이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 사고가 발생한다. 이러한 사고가 일어나면 공항의 평판이 급속히 나빠져, 이후 어떤 비행기도 도착하지 않으려 할 것이다." ㄴ> 어떤 곳에도 도킹하지 못하게 되면 지금껏 도킹한 비행기 수 출력하고 끝! 문제 풀이: 일단 가장 많이 비행기를 도킹하려면 도킹 할 수 있는 곳 중 가장 큰 수의 게이트에 도킹해야한다. 주어진 gi부터 1까지 빈 곳을 항상 다 ..