Program Programming Programmer

문제: https://www.acmicpc.net/problem/1932 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1)Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.Each step can go either diagonally down to the left or diagonally down to the right.The number of rows in the triangle is ≥ 1 but ≤ 500.The numbers i..

문제: https://www.acmicpc.net/problem/1149 memoization을 이용한 동적 계획법으로 풀 수 있는 문제입니다. 첫 번째 집을 칠할 때는 전에 칠한 집의 색이 없으므로 모든 색을 칠할 수 있기에 rgb 값 0~2이 아닌 3을 넘겨줍니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#pragma warning (disable:4996)#include #include #include #include using namespace std; int cost[1000][3];int cache[1000][4]; int dp(int curHouse, int preColor..

문제: 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/2688 문제A number is said to be made up of non-decreasing digits if all the digits to the left of any digit is less than or equal to that digit. For example, the four-digit number 1234 is composed of digits that are non-decreasing. Some other four-digit numbers that are composed of non-decreasing digits are 0011, 1111, 1112, 1122, 2223. As it turns out, there ar..

문제: https://www.acmicpc.net/problem/1038 완전탐색으로 문제를 풀 경우 시간 복잡도가 크기 때문에 다른 방법으로 접근을 해야 했습니다.만약 n이 19일 경우0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, 43위와 같은 순서대로 43이 정답이 되는데, 10 이후의 숫자들을 자세히 살펴보면앞자리가 4일 경우 올 수 있는 가짓수는 0, 1, 2, 3 사이의 숫자들 중 한 가지를 고르는 순서 없는 조합의 가짓수임을 알 수 있습니다.즉, 이항계수로 구할 수가 있습니다.따라서 다음과 같이 이항계수를 사용하여 시간 복잡도를 줄여 풀어볼 수 있습니다. 12345678910111213141516171819202122232..

문제: https://www.acmicpc.net/problem/1029 memoization과 bit mask 를 이용한 dynamic programming 방법과 재귀함수를 이용한 DFS 을 이용해 풀어봤습니다. my solvingc++1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include #include #include #include #include #include using namespace std; const int MAX_N = 15;int n;int prices[MAX_N + 1][MAX_N +..

문제: https://www.acmicpc.net/problem/1028 memoization 과 현재 최대값보다 작은 다이아몬드는 계산하지 않는 가지치기 방법으로 시간 복잡도를 줄여 풀었습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712..

문제: https://www.acmicpc.net/problem/1010 n 개 에서 k 개를 고르는 (순서 없는)조합의 가짓수를 구하는 이항계수를 구하는 문제입니다.특히 다리가 겹치면 안된다는 조건이 있기에 순서에 무관하게 조합의 개수를 구해야 됩니다. 이항 계수를 구하는 방법은 이전에 포스팅 한 방법을 사용해 구했습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include using namespace std; const int MAX = 31; int cache[MAX][MAX]; int getBinomialCoefficient(int n, int k..

문제: https://www.acmicpc.net/problem/1006 처음에는 brute force 로 풀어봤으나 최대 N 의 값이 10000 이기 때문에 시간이 초과됩니다. 따라서 memoization 방법을 사용해야 되는데 그러기 위해서는 1번부터 N - 1 까지 순차적으로 우측 방향으로만 진행하며 경우의 수를 찾아야 됩니다. 이때 문제는 1번과 N + 1번에서 왼쪽으로 진행되는 방향은 고려되지 않는다는 점이 문제입니다. 해당 부분에 대해 한참 고민을 하다 사이트의 질문 검색을 통해 하드 코딩을 하는 방법으로 조언을 얻어 해결 했습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243..

문제: https://www.acmicpc.net/problem/1005 처음에는 bruteForce 방법으로 풀었다가 시간 초과! 그래서 memoization 방법을 이용해 시간 복잡도를 줄여 풀었습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #include #include #include #include using namespace std; multimap techTrees;vector buildin..