:: ADVANCE ::

BAEKJOON ONLINE JUDGE 2842 집배원 한상덕 https://www.acmicpc.net/problem/2842 처음 접하는 이진탐색... 이라고 해야하나일단 처음 풀이는 이진 탐색 문제집에서 열어본 문제기 때문에 이진탐색이라는 점을 염두해 두고 풀이를 접근해 보았다. 또한 이전에 풀었던 '배열에서 이동' 문제가 생각나서 이와 비슷한 문제라고 생각을 하였다.but, '배열에서 이동'처럼 문제를 접근하기에는 고도 값이 매우 크기 때문에 time limit이 날 수 밖에 없다. 1. 다익스트라 일단 이진탐색으로 고도의 최소값을 정해놓고, 그 중 P에서 K로 가는 경로의 최대값을 파악했다.될 수 있는 최소 고도의 최대값을 이진탐색으로 찾고, 0부터 최소 고도의 최대값까지 다익스트라를 돌리면서 ..

BAEKJOON ONLINE JUDGE 2792 보석 상자 https://www.acmicpc.net/problem/2792 보석을 받지 못하는 학생도 있다 -> 보석은 꼭 배분해야 한다. 라고 해석최대값을 지정해 놓고 그 이하의 개수로 분배를 할 때 받는 학생의 수를 세서분배를 위해 필요한 학생의 수가 존재하는 학생의 수보다 많으면 -> 보석을 전부 분배할 수 없다 -> 최대값을 늘린다.분배를 위해 필요한 학생의 수가 존재하는 학생의 수보다 작으면 -> 보석을 전부 분배할 수 있다 -> 최대값을 줄일 수 있다.=> 이분탐색 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include int n..

BAEKJOON ONLINE JUDGE 3649 로봇 프로젝트 https://www.acmicpc.net/problem/3649 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #include using namespace std; int len;int n;int lego[1000001]; int bsearch(int num){ int s = 0, e = n - 1; int m; while (s

BAEKJOON ONLINE JUDGE 3079 입국심사 https://www.acmicpc.net/problem/3079 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include using namespace std; int n, m;int time[100001]; bool cmp(const int &first, const int &second) { return first > second;} int ispossible(long long t){ int num = m; int i = 0; while (i 0) { num = num - t / time[i]; i+..

BAEKJOON ONLINE JUDGE 3020 개똥벌레 https://www.acmicpc.net/problem/3020 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include #include using namespace std; int n, h;int bottom[100100], top[100100];int cut[500001]; int bsearch(int num){ int s = 0, e = n / 2 - 1; int m; int ans; while (s

BAEKJOON ONLINE JUDGE 10815 숫자 카드 2 https://www.acmicpc.net/problem/10816 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include using namespace std; int n;int card[500001]; int bsearch(int num){ int s = 0, e = n - 1; int m, cnt = 0; while (s

BAEKJOON ONLINE JUDGE 1620 나는야 포켓몬 마스터 이다솜 https://www.acmicpc.net/problem/1620 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include using namespace std; int n, m;int index[100001];char pocketmon[100001][21]; bool cmp(const int &first, const int &second){ string F = pocketmon[first]; string S = poc..

BAEKJOON ONLINE JUDGE 10815 숫자 카드 https://www.acmicpc.net/problem/10815 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include using namespace std; int n;int number[500001]; int bsearch(int num){ int s = 0, e = n - 1; while (s

BAEKJOON ONLINE JUDGE 1939 중량제한 https://www.acmicpc.net/problem/1939 입력되는 제한 중량 최대값 사이정답찾아가는 이분 탐색 + bfs 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include #include #include using namespace std; int n, m;int start, dest;vector graph[100001];int visit[100001];queue que; void init() { for (in..

BAEKJOON ONLINE JUDGE 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 아 어렵다... 다이나믹도 해보고 dfs도 해보고 dfs 완탐은 time limit 나고. 뭐 time limit 날거라는 거는 예상했지만... 결국 해답 소스 보고함ㅠ 1. 이진 탐색으로 최대-최소 차이를 찾아나간다. 이진 탐색의 지표는 이진 탐색으로 정한 최대-최소 차이 내로 (1, 1)에서 (n, n)으로 갈 수 있느냐 (1, 1) -> (n, n) 갈 수 있느냐는 bfs로 탐색 2. bfs 최대-최소를 살펴보면서 가려면 지나온 경로들의 최대, 최소를 가지고 있어야 한다 but, 이렇게 접근하다가 다이나믹도, 완탐도 틀렸다ㅠ.ㅜ => map을 가장 작은 값에서 가장 작은 ..