Program Programming Programmer

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

문제: https://www.acmicpc.net/problem/2703 문제A cryptoquote is a simple encoded message where one letter is simply replaced by another throughout the message. For example:Encoded: HPC PJVYMIYDecoded: ACM CONTESTIn the example above, H=A, P=C, C=M, J=O, V=N, Y=T, M=E and I=S. For this problem, you will decode messages.입력The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the..

문제: https://www.acmicpc.net/problem/2702 문제In sixth grade, students are presented with different ways to calculate the Least Common Multiple(LCM) and the Greatest Common Factor (GCF) of two integers. The LCM of two integers a and b is the smallest positive integer that is a multiple of both a and b. The GCF of two non-zero integers aand b is the largest positive integer that divides both a and b..

문제: https://www.acmicpc.net/problem/2700 문제A lattice point is a point with integer coordinates. A lattice polygon is a polygon with all vertices lattice points. The lattice points on the boundary of the polygon are boundary points (open dots in the figure above) and the points inside and not on the polygon are interior points (filled in dots in the figure above). A polygon is convex if any line ..