:: ADVANCE ::

BAEKJOON ONLINE JUDGE 1162 도로포장 https://www.acmicpc.net/problem/1162 다익스트라 + DP평소 다익스트라는 그냥 그래프의 개수만큼 정점을 탐색하는데,이 visit 정점 배열을 DP 배열로 놓고, DP[도시 개수][포장 가능 도로의 수]로 놓고 풀면 된다.다익스트라 구현 시 반복문 안에는 다른 도시로 영역을 넓힐 때 포장가능 할 때 포장하는 경우와 포장을 하지 않는 경우 둘 다 queue에 넣어주어 구현하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727..

BAEKJOON ONLINE JUDGE 1365 꼬인 전깃줄 https://www.acmicpc.net/problem/1365 LIS 문제최장 증가 부분 수열의 개수만큼이 잘 연결된 것이고, 나머지를 잘라주면 최소가 된다.잘은 모르겠지만 직접 예제를 만들어보고 알게됨.. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include int n;int size = 1;int lisArr[100000]; void lis(int num){ int s = 0, e = size, middle; if (lisArr[size - 1]

dovelet LIS http://183.106.15.130/30stair/LIS/LIS.php?pname=LIS C - 이진탐색 구현 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include int n;int num[500000];int parent[500000];int lisArr[500000];int size; void lis(int idx){ int s, e, middle; if (num[lisArr[size - 1]]

Algospot Longest Increasing Sequence https://algospot.com/judge/problem/read/LIS 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include int n;int lisarr[500], input[500];int size; void init(){ int i; for (i = 0; i

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2012 2532 먹이사슬 https://www.acmicpc.net/problem/2532 1. 정렬선의 왼쪽 시작지점을 기준으로 정렬한다.왼쪽 시작지점은 오름차순으로, 왼쪽 시작지점이 같을 경우에는 오른쪽 끝 지점이 작은순으로 (내림차순)으로 정렬한다.2. 문제의 조건을 보면 같은 시작점, 같은 끝점을 지는 선분은 포함하지 않는다. 하지만 입력으로 들어올 수 있기 때문에 이를 무시해 준다.3. LIS (최장 길이 증가 부분 수열 Longest Increasing Subsequence)정렬한 값을 순서대로 LIS O(NlogN)을 구현한다. O(N^2)은 time limit난다. LIS (O(NlogN))은 이진탐색을 이용하여 구..

BAEKJOON ONLINE JUDGE 한국정보올림피아드 2011 2437 저울 https://www.acmicpc.net/problem/2437 [참고] 그리디 저울 알고리즘_naver blog 저울의 값을 오름차순으로 정렬하고 하나씩 늘려가면서 무게를 잰다.원리 : n개의 저울을 다 사용한 무게 < 새로운 저울 이면 그 사이에 존재하는 무게는 잴 수 없다.n개의 저울을 사용하여 잴 수 있는 무게는 그 이전 무게 또한 부분 개수의 저울을 이용하여 잴 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include int n;int num[1001]; void quicksort..

BAEKJOON ONLINE JUDGE 1920 수 찾기 https://www.acmicpc.net/problem/1920 이진 탐색 아.. 왜 나는 이진탐색 구현을 매번 실수하지.. quicksort 구현하면 0부터 마지막 배열까지 stl::sort : 0부터 마지막 + 1까지 (개수)binary search도 마찬가지로 left : 0, right : n - 1 까지 해야하는데 자꾸 n까지로 해서 값이 하나 잘못 들어가는 실수... 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include int a[100010];in..

BAEKJOON ONLINE JUDGE 2240 자두나무 https://www.acmicpc.net/problem/2240 DP처음에 bottom-up으로 접근했다가 틀려서일단 top-down으로 먼저 풀음 어떤 시간에 어떤 나무에 있을 경우에는 이전에 같은 나무에 있었다가 그대로 기다린 경우, 이전에 다른 나무에 있었다가 옮겨서 지금의 나무에 있는 경우가 존재하므로 이 둘 중에 큰 값을 가져와야 한다. 그리고 지금 있는 나무의 위치에서 자두가 떨어지면 +1, 아니면 그냥 있는 걸로 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #define Max(x, y) (((x) > (y)) ? (..

BAEKJOON ONLINE JUDGE 1535 안녕 https://www.acmicpc.net/problem/1535 0-1 knapsack 문제체력이 100까지므로 100에서 깎아도 되고0에서 인사를 할 때 체력을 쌓아서 100이전, 99로 만들때 저장되는 기쁨의 최대값을 출력 strength[1]을 사용할 때 모든 체력에 저장된 기쁨에 joy[1]을 합해가면 점차 쌓여서 체력 99에 모든 값이 저장되어 있다. 12345678910111213141516171819202122232425262728293031#include #define Max(x, y) (((x) > (y)) ? (x) : (y)) int n;int strength[20], joy[20];int dp[100]; int main(){ i..

BAEKJOON ONLINE JUDGE 2411 아이템 먹기 https://www.acmicpc.net/problem/2411 DP이동은 오른쪽, 위쪽만 가능하다 -> scv 문제와 비슷아이템을 모두 먹어야 한다 -> 아이템을 먹으러 들려야 한다. 아이템 있는 곳으로 갈 때는 한 아이템에서 다른 아이템이 있는 위치로 이동하는 부분 경로, 부분 이동 경우의 수로 생각. 최종적으로는 각 아이템을 먹으러 이동하는 부분 경로를 곱하면 된다. 장애물이 있는 곳은 못가는 곳이므로 경로값 0오른쪽, 위쪽만 가능하므로 시작 지점의 왼쪽과 아래는 갈 수 없는 부분. 경로값 0시작은 (1, 1), 마지막은 (n, m) 그리고 C++에서 vector를 쓸 때, >>에서 꼭 사이를 띄어주어야 컴파일 에러가 나지 않는다. 매번..