본문 바로가기

알고리즘225

BOJ 7579 - 앱 (knapsack[+]) https://www.acmicpc.net/problem/7579 2차원 구조->1차원 구조 설명 한 동전을 단 한번 사용해야 하는지, 여러번 사용할 수 있는지 앱을 끄면 메모리와 비용이 각각 늘어난다. (메모리 m; fill(dp, dp + MAX, 1e9); for (int i = 0; i > b[i]; //메모리 for (int i = 0; i > c[i]; //비용 dp[0] = 0; for (int i = 0; i = 1; j--) if(j-b[i]> m; for (int i = 0; i > b[i]; for (int i = 0; i > .. 2020. 2. 25.
BOJ 16764 - Cowpatibility (포함배제, 부분집합) https://www.acmicpc.net/problem/16764 https://acm-iupc.tistory.com/8 i번째 소에 대한 정보가 들어올 때, 1번~i-1번소 중 i번 소와 compatible한 쌍의 개수를 세준다. 어디서? 부분집합을 만드는 코드에서 이때, 포함배제를 사용할 부분은 1~i-1번 소이기때문에 mp[v]는 나중에 ++해준다. ll n, a[5], r; map mp; int main() { cin >> n; for (int j = 0; j > a[i]; sort(a, a + 5); for (int x = 1; x < (1 2020. 2. 25.
BOJ 17026 - Mountain view (라인스위핑) https://www.acmicpc.net/problem/17026 전체선분의 개수에서 어떤 선분에 완전히 포함되는 선분의 개수를 뺀 나머지를 구해라. (입력 x,y면 선분은 [x-y, x+y]) 선분 [l,r] n개에 대해 l기준으로 오름차순 정렬하되 l이 같다면 r기준 내림차순 정렬한다. 선분들을 차례로 돌면서 r의 최대값을 mx에 유지하고 mx보다 크다면 ans++해준다. 어떤 선분에 포함되는 선분의 개수를 구하고싶다면? n-ans int n; P p[MAX]; int main() { FAST; cin >> n; for (int i = 0,x,y; i > x >> y; p[i].first = x - y, p[i].second = x + y; } sort(p, p + n.. 2020. 2. 24.
BOJ 17038 - The great revegetation (유니온 파인드, 이분그래프) https://www.acmicpc.net/problem/17038 그래프가 이분그래프인지 아는법 기록 + 온라인쿼리 풀이 숙지 최대 1e5개의 목초지 n개가 있다고 할 때, 소(쿼리) m개가의 정보가 들어온다. 목초지는 두 그룹으로 나뉜다. S a b : a,b목초지가 같은 그룹에 있어야 해. D a b : a,b목초지가 다른 그룹에 있어야 해. 모든 목초지를 나누는 경우의 수를 구하라 오프라인 쿼리. s먼저 입력해서 merge해두고 d를 입력받으면서 a,b의 대표값을 간선으로 이어준다. 그래프가 이분그래프라면 컴포넌트마다 그룹을 나누는 경우가 두가지이므로 2^컴포넌트의 수가 정답. 그래프가 이분그래프가 아니면 그룹을 나눌 수 없다. int n, m, uf[MAX], vst[MAX]; vector ad.. 2020. 2. 22.

티스토리툴바