Program Programming Programmer

문제: https://www.acmicpc.net/problem/2343 이진 탐색으로 풀 수 있는 문제입니다. 필요한 블루레이의 개수가 m보다 많을 경우 low 를 높여 블루레이의 크기를 크게 만드는 방향으로 탐색을 하고 필요한 블루레이의 개수가 m과 같거나 더 작을 경우 블루레이의 크기를 작게 만드는 방향으로 탐색을 해서 최적의 값을 구하면 됩니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#pragma warning (disable:4996)#include #include #inc..

문제: https://www.acmicpc.net/problem/2792 문제A marble factory has donated a large box of marbles to a kindergarten. Each marble has one out of M different colours. The governess needs to divide all the marbles between the N children in her group. It is acceptable if some children don't get any marbles. However, no child wants marbles of different colours – in other words, all marbles that a child ..

문제: https://www.acmicpc.net/problem/1072 앞선 문제들과 같이 이진 탐색으로 쉽게 풀 수 있는 문제입니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#pragma warning (disable:4996)#include #include #include #include using namespace std;typedef long long ll; bool isChanged(int x, int y, ll mid){ ll oldValue = (ll)y * 100 / x; ll newValue = (mid + (ll)y) * 100 / (x + mid); return n..

문제: https://www.acmicpc.net/problem/3079 문제The Croatian delegation, consisting of M people, is travelling to IOI 2013 in Australia. They are currently waiting in a queue for check-in at the airport. There are N check-in desks open. Some officials work more efficiently than others, so the desks operate at different speeds. At the k-th desk, Tk seconds are required to finish check-in of a single p..

문제: https://www.acmicpc.net/problem/2110 랜선 자르기와 비슷한 방법으로 풀 수 있는 문제입니다. 공유기를 원래 설치하려는 개수와 같거나 더 많이 설치할 수 있는 조건하에서 최대 간격을 구해야 되는 문제입니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#pragma warning (disable:4996)#include #include #include #include using namespace std;typedef long long ll; ll getRouterNumber(const int* numbers, i..

문제: https://www.acmicpc.net/problem/1654 우선 만들어진 랜선의 개수가 필요한 개수보다 크거나 같은 경우 최대값을 답으로 구하기 위해 비교 부분에서 일반적인 이진탐색과 다르게 구현을 해야 됩니다. 그리고 많이 틀릴 수 있는 부분이 오버 플로인데 랜선의 길이는 2^31-1보다 작거나 같은 자연수이기 때문에 low 와 high 를 합하는 과정 등에서 오버 플로가 발생할 수 있으니 비교 관련 변수는 모두 long long 으로 선언을 해두는게 안전합니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#pragma warning (disable:499..

문제: https://www.acmicpc.net/problem/2512 계산된 예산의 합이 상한 예산과 같을 경우 해당 값이 답이 되고 그렇지 않는 범위 내에서 최대값을 구해야되므로 이진탐색으로 쉽게 풀 수 있는 문제입니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#pragma warning (disable:4996)#include #include #include #include using namespace std;typedef long long ll; ll getSumBudget(const int* numbers, int maxBudget, int n){ ll ret = ..

문제: https://www.acmicpc.net/problem/2805 문제Lumberjack Mirko needs to chop down M metres of wood. It is an easy job for him since he has a nifty new woodcutting machine that can take down forests like wildfire. However, Mirko is only allowed to cut a single row of trees.Mirko‟s machine works as follows: Mirko sets a height parameter H (in metres), and the machine raises a giant sawblade to that h..

문제: https://www.acmicpc.net/problem/10815 1920번 수 찾기 문제와 같은 문제네요. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#pragma warning (disable:4996)#include #include #include using namespace std; int binarySearch(const int* numbers, int target, int n){ int low = 0; int high = n - 1; while (low target) high = mid - 1; else if (target > numbers[mid]) low = mid + 1; e..

문제: https://www.acmicpc.net/problem/1920 이진탐색을 사용하는 문제입니다.사실 std::binary_search 을 사용하면 아주 짧고 간단하게 풀 수 있습니다. 하지만 이진탐색을 직접 만들어서 풀어보는 것도 좋을 것 같네요.그리고 주의할 점은 cin 이 scanf 보다 시간복잡도가 높은데 cin 을 사용하면 시간 초과가 발생합니다.마지막으로 이상한 점 하나는 제 코드 상에서의 compare 을 사용한 qsort 을 이용해서 정렬할 경우 오답처리가 됩니다. 그 이유는 아직 잘 모르겠네요.... 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#pragma..