블로그 옮겼습니다

https://csacademy.com/contest/round-36/task/tree-nodes-sets/ N p; G[p].push_back(i); } for(int i = 1; i > K; for(int j = 0 ; j > a; oper[i].push_back(a); } } dfs(1, stt); for(int i = 1 ; i

https://www.acmicpc.net/problem/1804 2*B 격자에 음식이 N개 놓여져 있다. K개의 랩을 사용하여 음식을 덮을 때 덮이는 칸의 최소 개수를 구하는 문제이다. 랩은 어느 크기로든 늘리거나 줄일 수 있다. N > K >> B; for(int i = 0 ; i > r >> c; mp[c] = mp[c] | (1

https://www.acmicpc.net/problem/11570 N N; for(int i = 0 ; i > A[i]; cout

https://www.acmicpc.net/problem/14437 정수 S 와 문자열 str 가 입력으로 주어진다. S

http://codeforces.com/contest/822/problem/C n과 k가 주어진다.n은 비행기 티켓의 개수 이다. 각 티켓에는 l,r,c 세개의 정수가 있고 l은 출국일, r은 입국일, c는 티켓 가격이다.범위는 l,r l >> r >> c; v.push_back(ticket{l,r-l+1,c,0}); v.push_back(ticket{r,r-l+1,c,1}); } sort(v.begin(), v.end()); ll ans = infl; for(int i = 0 ; i

길이가 3인 단순경로일 때는 그래프 모양이 예외적으로 살짝 다르지만 4부터는 a개가 붙어있는 두 노드 사이의 노드개수만늘어날 뿐, 모양이 같다는 사실을 알 수가 있다. 예제: Three Tree (길이가 3인 단순경로의 개수N이 입력으로 주어질 때 트리 아무거나 하나 만들어 출력)http://lavida.us/problem.php?cid=1496&pid=4

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3883 노드가 N개인 트리가 주어진다. 트리의 각 노드에 최대 한개의 식물을 놓아 간선들을 보호해야한다.식물은 세가지가 있다. 1번 : $100 이며 인접한 간선 하나 보호가능2번 : $175 이며 인접한 간선 두개 보호가능3번 : $500 이며 인접한 모든 간선 보호가능 간선을 모두 보호하기 위해 필요한 최소 비용을 구하는 문제이다. dp[i][j] : i는 현재 노드, j는 나의 부모를 연결하는 엣지를 부모가 보호해줬는지 여부 true/false 일 때인접한 간선을 모두 보호하기 위한 최소 비용 이라고 부분문제를 정의해 보자. 그럼 dp[i][0] 은 ..

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4153 n개의 노드로 이루어진 트리가 있고 간선에는 기중치가 있다.q개의 쿼리가 주어진다.각 쿼리마다 연료의 양 x가 주어진다.루트노드부터 시작하여(루트 노드는 암시적으로 결정되어있음) 연료 x로 방문할 수 있는 최대 노드의 수를각 줄에 출력한다. 이 문제는 트리 dp 문제인데 부분문제를 두개 정의해야 한다. dp1[i][j]= 노드 i를 루트로 하는 서브트리에서부터 (현재노드포함) j개의 노드를 방문하고 돌아오는 최소비용 dp2[i][j]= 노드 i를 루트로 하는 서브트리에서부터 (현재노드포함) j개의 노드를 방문하고 안돌아와도 되는 최소비용 dp1은 d..

http://codeforces.com/contest/821/problem/E (0,0) 에서 (k,0) 까지 가는 방법의 수를 구하는 문제이다.이동을 할 때에는 세가지 방법이 가능하다. (x,y) 에서 (x+1,y-1), (x+1,y), (x+1, y+1) 이렇게 세가지 이동이 가능하다.대신 n개의 선분이 주어진다. 구간은 ai, bi, ci 로 표현되며y좌표가 ci 이면서 x좌표가 [ai,bi] 인 선분이다. 출발지에서 도착지까지 갈 때이 선분을 넘어가면 안된다. \(b_i = a_{i+1} \) 라는 조건과 \(a_n \le {k}\le{b_n}\) 라는 조건이 주어진다.그리고 ci 는 최대 15이며 ai,bi,k 는 10^18 이하이다. 뻔한 행렬 dp 이다. 12345678910111213141..

사실 이건 너무 당연한건데 이 문제 에서 다른 복잡한 식안에 변형되어 숨어있으니까고보면 이 포스팅의 제목과 같은 문제라는 것을 파악하지 못하여 이 글을 메모삼아 올린다.가장 무식한 방법은 O(N^2) 로 모든 쌍을 봐주어 최소값을 갱신하는 것이다.그런데 사실 그냥 N개의 수 중에 가장 작은 두 수의 합이 답이 될 것이다. 그럼구현하기에는 정렬하여 0번째, 1번째 값의 합을 구하는 O(NlgN) 방식이 제일 깔끔하다.O(N) 에 구현하려면 사실 두개의 변수를 두어 구현할 수는 있지만 구현 방법에 따라조건문 처리해주는게 뭔가 귀찮을 수도있다. 이렇게도 한번 생각해 보자.m = 0~i-1 원소들중 최소값이기 때문에 m+A[i] 로 답을 갱신하고m = min(m, A[i]) 로 m을 갱신하는 식으로 반복문을 돌..