Program Programming Programmer

문제: 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/10816 쉽게 자료구조 std::map 을 사용하는 것이 편한 문제네요. 1234567891011121314151617181920212223242526272829#pragma warning (disable:4996)#include #include #include #include #include using namespace std; int main(){ int n, m, num; map numbers; scanf("%d", &n); for (int i = 0; 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/2869 문제There is a snail on the ground. It wants to climb to the top of a wooden pole with the height of V meters, measuring from the ground level. In one day it can climb A meters upwards, however during each night it sleeps, sliding B meters back down. Determine the number of days it needs to climb to the top. 입력The first and only line of input contains three..

문제: 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..

문제: https://www.acmicpc.net/problem/2193 dynamic programming 방법 중 하나인 memoization 으로 쉽게 풀 수 있는 문제입니다. 우선 이친수를 구할 수 있는 재귀함수를 만들고 memoization 을 사용하는 방법으로 풀었습니다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include #include #include using namespace std;typedef long long ll; ll cache[91][2];ll getPinaryNumber(int digit, int num){ if (digit == 1) return 1; ll& ret..

문제: https://www.acmicpc.net/problem/1629 주어진 a, b, c 의 값이 크기 때문에 시간 복잡도를 줄이기 위해 분할 정복을 사용하고, 오버 플로를 방지하기 위해 중간에 얻어지는 값을 c 로 나눠가며 풀어봤습니다. 123456789101112131415161718192021222324252627282930#include #include #include #include #include using namespace std;typedef long long ll; ll multiply(ll a, ll b, ll c){ if (b == 0) return 1; int multi = multiply(a, b / 2, c); if (b % 2 == 0) return multi * mult..