:: ADVANCE ::

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를 쓸 때, >>에서 꼭 사이를 띄어주어야 컴파일 에러가 나지 않는다. 매번..

BAEKJOON ONLINE JUDGE 11052 붕어빵 판매하기 https://www.acmicpc.net/problem/11052 DPdp[n] = Max(i개 세트 가격 + 나머지 붕어빵 개수의 최대값) 1. top-down 12345678910111213141516171819202122232425262728293031323334353637#include #define Max(x, y) (((x) > (y)) ? (x) : (y)) int n;int cost[1001];int dp[1001]; int solve(int num){ int i; if (num == 0) return 0; if (dp[num]) return dp[num]; dp[num] = cost[num]; for (i = 1; i

BAEKJOON ONLINE JUDGE 11507 오르막 수 https://www.acmicpc.net/problem/11057 오르막 수1. dp[ n 번째 수가 ] [ i 일 때 ] 오르막 수 = n - 1번 째수가 i보다 같거나 큰 수들의 오르막 수들의 합 즉, 5자리 수 일 때 첫째 자리에 1이 오면 두번째 자리에 1, 2, 3, .... 9가 올 수 있고, 이 수들을 처음 수로 하는 4개의 오르막 수들이 다 올 수 있기 때문에 모든 그러한 경우의 수들을 다 합하면 된다. 12345678910111213141516171819202122232425262728293031323334353637#include int n;int dp[1001][10]; int solve(){ int i, j, k; int..

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2005 2594 놀이공원 https://www.acmicpc.net/problem/2594 풀이 > 입력된 시간을 -10분, +10분 해서 저장한 후운행 시작 시간을 기준으로 정렬그 후 운행 시간을 시작과 종료 시간을 이어나가는데 가장 늦게 끝나는 시간과 이어지지 않는 시작시간을 만나면 rest time으로 계산 및 최대값 찾기 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include using namespace std; struct Data { int start, end;};..

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2005 2593 엘리베이터 https://www.acmicpc.net/problem/2593 1차 풀이 : DPinput을elevator[층] : 각 층에서 갈 수 있는 엘리베이터 번호fl[엘리베이터 번호] : 각 엘리베이터에서 갈 수 있는 층들을 vector로 저장 dp[floor][elevator] : floor를 elevator로 도착할 때의 최소 이동 (floor 없어도 될 듯)이동할 때 각 elevator를 중점으로 이동 요즘 DP 공부 중이라 DP 적으로 접근했는데 over한 듯...답이 맞기는 하였지만 시간이 60ms가 나오기도 했고 이 풀이는 영 아닌것 같아서 다시 접근 1234567891011121314151617..