:: ADVANCE ::

BAEKJOON ONLINE JUDGE 12758 천상용섬 https://www.acmicpc.net/problem/12758 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include #include #include #include using namespace std; #define MOD 1000000007 int dp[310][300];vector mnt[310];int n; void input(){ int i, j; int num; scanf("%d", &n); for (i = 1; i

BAEKJOON ONLINE JUDGE 12852 1로 만들기 2 https://www.acmicpc.net/problem/12852 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include int dp[1000001];int output[1000001]; int solve(int n){ int min = 2147000000; int temp, out; if (dp[n] != -1) return dp[n]; if (n % 3 == 0) { temp = solve(n / 3); if (temp

BAEKJOON ONLINE JUDGE 한국정보올림피아드 2002 2169 로봇 조종하기 https://www.acmicpc.net/problem/2169 왼쪽, 오른쪽, 아래로만 이동 -> 윗줄 까지는 최적한 지점을 갈 때 왼쪽에서, 오른쪽에서, 위에서 가장 최대값 + 그 위치의 가치이 때 이전 지점들은 예를들어 왼쪽에서 왔으면 그 지점은 그 왼쪽과 위만 경로롤 가질 수 있다 -> 중복탐색이 안되기 때문에따라서 탐색할 때 한 줄을 위와 왼쪽에서 올 수 있는 값을 미리 저장, 오른쪽에서 올 수 있는 값을 따로 저장한 후 최종적으로 이 둘 중 Max값을 저장하면 최적의 값이 저장된다.첫째 줄은 위와 오른쪽으로는 경로로 삼을 수 없다계속 틀려서 1시간 30분 걸림 123456789101112131415161..

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