dynamic programming 10

BAEKJOON 1932 - 숫자삼격형

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

BAEKJOON 1149 - RGB거리

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

BAEKJOON 2193 - 이친수

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

BAEKJOON 2688 - Non-Decreasing Digits

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

BAEKJOON 1038 - 감소하는 수

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

BAEKJOON 1029 - 그림 교환

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

BAEKJOON 1028 - 다이아몬드 광산

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

BAEKJOON 1010 - 다리 놓기

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

BAEKJOON 1006 - 습격자 초라기

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

BAEKJOON 1003 - 파보나치 함수

문제: https://www.acmicpc.net/problem/1003 파보나치를 구할 수 있는 재귀함수에서 0 과 1인 경우가 불리는 횟수는 나열을 해보면0의 경우 주어진 n - 1 의 파보나치 수1의 경우 주어진 n 의 파보나치 수와 같다는 것을 알 수 있습니다.그리고 파보나치 수의 경우 n이 커지면 시간복잡도가 매우 커지기 때문에 memoization 을 사용해 시간 복잡도를 줄여 풀었습니다. my solvingc++1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include using namespace std; map cache;int fibonacci_dp(in..