목록Algorithm (121)
블로그 옮겼습니다
길이가 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을 갱신하는 식으로 반복문을 돌..
N개의 컴포넌트들이있고 판떼기가 하나있다. 판떼기는 앞면과 뒷면이있다. 각 컴포넌트를 판떼기에 모두 붙이고싶은데 하나의 컴포넌트를 앞면에 붙이는 비용과 뒷면의 붙이는 비용은 다르고각 컴포넌트마다도 비용이 또 다르다.그리고 특정 컴포넌트들은 무조건 앞면 혹은 뒷면에 부착해야 된다는 조건이 주어진다.-1 이면 뒷면에, 1이면 앞면에 붙여야하며 0이면 어떤면에 붙여도 상관없다는 것이다.그리고 M개의 제한이 주어지는데 각 제한의 내용은 특정 두 컴포넌트를 다른 면에 붙였을 때에는추가적인 비용이 발생한다는 것이다. 각 제한마다 두 컴포넌트와 추가 비용은 다르다.이 때 N개의 컴포넌트를 모두 판떼기에 붙이는 최소 비용을 구하여라. 이 문제는 min-cut 문제이다. source -> 컴포넌트 -> sink 와 같은..
http://codeforces.com/contest/821/problem/D \(n,m,k\le{10^4}\)세로 n, 가로 m 인 n * m 크기의 격자판의 (1,1) 에서 (n,m) 까지 이동하고싶다.격자판의 k개의 칸에는 불이 켜져있다. (1,1)은 무조건 켜져있다. 이동할 때에는 무조건 불이 켜져있는 칸만 밟을 수가 있다.하지만 코인 1개를 사용하면 한 행 전체, 혹은 한 열 전체의 불을 켤 수가 있다.한번에 하나의 열 또는 행만 켤 수가 있으며 만약 불을 켜는 행이나 열을 바꾸고 싶다면원래 부터 불이 켜져있던 칸으로 이동을 해야 한다. 물론 바꾸면 이전에 켠 행(열)은 원래 켜져있던 칸을 빼고는 다 꺼지고 새로운 행(열)이 켜지며 또 코인 1개가 든다.이 때 (1,1) 부터 (n,m) 까지가는..
https://csacademy.com/contest/archive/task/second-minimum/ 반씩 나눠가며 각각의 l, r 에 대해 작은 값을 가지고 있다면 한번 분할정복 돌리면 가장작은 값은 바로 나오며그다음에 토너먼트의 승패표가 있을 때 2등의 후보는 lgN개로 정해져있는 성질이 있기 때문에 다시 순회하면서lgN개에 대해서만 반복문 한번 돌리면서 가장 작은놈을 구해주면 된다.2등의 후보는 결승에서 1등한테 진놈, 준결승에서 1등한테 진놈, 준준결승에서 1등한테 진놈, ..... ,1라운드에서 1등한테진놈이 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include using namespa..
https://algospot.com/judge/problem/read/COUNTPALIN \( 1\leq{N}\leq{10^6} \)길이가 N인 문자열 S가 입력으로 주어질 때 팰린드롬인 모든 부분 문자열의 개수를 구하는 문제이다.이 문제를 푸는 방법은 우선 각 중심마다 최대 팰린드롬의 길이를 구한뒤 그 길이/2 만큼을 모두 더해주는 것이다.왜냐하면 어떤 중심에서 최대 길이의 팰린드롬이 abccba 라면 같은 중심을 가지는 팰린드롬들은 반지름을 1씩 줄여나가면모두 팰린드롬이기 때문에다. 이것은 자명하다. 즉, abccba, bccb, cc 이게 다 팰린드롬이 되기 때문에 최대팰린드롬길이/2의 식이 나오는 것이다. 그리고 중심이 다르면 다른 팰린드롬이라는 것이 자명하기 때문에 모든 각각의 중심에 대해최대..
N 명의 사람이 각각 선물을 하나씩 준비해왔을 때 모두가 자신이 준비한 선물 이외의 선물을 갖도록 나눌 때그 경우의수를 구하는 문제 1 2 3 4 5 다섯명의 사람이 있다고 가정하자.맨 처음에 1번사람은 자신의 선물이 아닌 나머지 사람들의 선물, 즉 n-1 개의 선물을 가질 수 가 있다.그럼 그중에 하나의 경우인 1번사람이 2번사람의 선물을 가질 때를 생각해보자.그럼 2번사람이 받는 선물은 두가지 경우로 나뉜다. 첫번째, 1번사람의 선물을 갖는 경우. 그럼 1번 사람과 2번사람이 선물을 둘이 교환한 것과 같게 되므로D[i] : i명의 사람이 자신의 선물을 안갖도록 선물을 교환하는 경우의수일때, 교환한 두명을 제외한 나머지 n-2명에게 같은 행위를 반복하므로 D[n-2] 가 된다. 두번째, 1번 사람이 아..