Approach 이 문제에 대해서 잘 고찰해보면, 어떤 기업이 선택되는 것은 이전 기업에 얼마만큼의 투자했는지에 의해서 결정된다. 따라서 이러한 측면에서 관계식을 통해 표현할 수 있으므로 DP라고 인식해야 한다. Let $dp[i][j]$ : the amount of maximum profit when we investing exactly $j$ until considering $i$'th element $dp[i][j] = \underset{k \in R, \forall k \in [0,j]}{max}(dp[i - 1][j - k] + b[i][k])$ 즉, i번째 기업까지를 고려해서 투자할 때, i - 1번째 까지의 투자 데이터를 가지고 있으면 된다. 그렇게 되면 투자 금액이 동일할 때, 최대의 이익..

Dynamic programming이란? 복잡한 문제를 여러 간단한 문제로 쪼개서 푸는 것 기본적으로 고등학교 때 학습하였던, 점화식을 활용하여 푸는 방법론이라고 이해해도 무방한다. 구현 방법 구현 방법은 크게 2가지가 있다. 반복분 장점 빠르고 메모리 측면에서 이득을 본다. DP 최적화 작용이 쉽다. (덱 DP, 세그 DP) 단점 테이블을 채우는 순서를 고려해야 한다. 순서가 복잡한 경우 사용하기 어렵다. (트리 DP, 비트 DP) 재귀 (Memoization을 사용) 장점 DP를 채우는 순서를 고려하지 않아도 되나, memoization을 사용하여 동일 반복 계산을 피한다. 순서가 복잡한 경우에도 처리하기 쉬움 (트리 DP, 비트 DP) 단점 반복문에 비해 느리고 메모리가 많이 든다. DP 최적화 작..

i번째까지의 집을 칠하기 위한 비용을 구하기 위해서는 i - 1번째 집의 색칠 상태가 필요하다 즉, dp[i][0~3] = i번째 index까지 칠했을 때 필요한 비용 (단, i번쨰 index를 칠한 색이 0이면 R, 1이면 G, 2이면 B) 따라서 점화식을 세워보면 구하고자 하는 답을 간단하게 구할 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int dp[1001][3]; int main(void){ fastio; memset(dp, 0, sizeof(dp)); int n; cin >> n; cin >> dp[0][0] >> dp[0][1] >> dp[0][2..

문제 자체는 그렇게 어렵지 않다. i번째에서 거리는 사실상 i-1번째의 상태에 의해서 결정되는 양상으로 진행된다. 추가적으로 조건을 잘 살펴보면 i분째 상태는 지침지수와 운동상태인지/쉬는 상태인지 여부에 따라 결정된다. 따라서 이러한 측면에서 3차원 DP가 필요하게 된다. dp[i][j][k] = i번째 분이 지났을 때 지침 지수가 j일때 달린 거리(단, k가 0이면 i번째 분일 때 쉰 상태, 1이면 달린 상태) 그리고 조건을 활용해서 점화식을 잘 세우면 다음과 같다. (단, d[i]는 i번째분에서 달릴 경우 갈 수 있는 거리) 1) 현재 움직히고 있는 상황인 경우(k가 1) dp[i][j][1] = dp[i - 1]j - 1][1] + d[i]가 기본적인 상황이다. 단, 만약 j가 1인 경우에는 dp[..

잘 생각해보면 10^6까지이므로 충분히 모두 다 조사해도 시간안에 무조건 들어온다. 다만, 중복되는 계산이 엄청나게 많을 것 처럼 보이므로 DP를 활용해서 중복되는 계산을 줄이는 것이 이 문제의 핵심이다. "dp[n] : 정수 N이 주어졌을 때 연산을 활용해서 1을 만들 수 있는 횟수의 최솟값" 이라 잡으면 점화식은 dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]이다. 다만, dp[1] = 0, dp[2] = 2; dp[3] = 4는 Base case이므로 따로 넣어준다. #include #include #include #include using namespace std; int dp[1000001]; int recursion(int n){ if(n == 1 || n == 2 ..

dp[n] : 정수 n을 1, 2, 3의 합으로 나타내는 방법 점화식 dp[n] = dp[n - 1] + dp[n - 2] + dp[n -3] 단, dp[1] = 1, dp[2] = 2, dp[3] = 4는 Base input 값이므로 따로 설정해준다. 잘 생각해보면 시작은 1, 2, 3일수 밖에 없고 그 뒤는 dp의 다른 값으로 표현함으로써 점화식을 세울 수 있다. #include #include #include #include typedef long long ll; using namespace std; ll dp[1000001]; ll sum(int n){ if(n == 1 || n == 2 || n == 3) return dp[n]; if(dp[n - 1] == 0) sum(n - 1); retur..

재미있는 문제이다. 15는 3의 배수와 5의 배수 성질을 모두 가지고 있다. 즉 자릿수를 다 더한것이 3의 배수이고, 끝이 5아니면 0이다. 이러한 성질을 이용해서 DP로 풀어주면 쉽게 해결할 수 있다. 잘 생각해보면 N번째 자리는 무조건 1, 5로 시작할 수 밖에 없다. 마찬가지로 N-1번쨰 자리는 무조건 1, 5로 시작할 수 밖에 없다. 이를 활용하여 자릿수가 3이라는 것과 결부지어 생각해보자 "DP[n] : n번째 자리일 때 15배수의 갯수"로 잡았다고 하였을 때 맨 앞자리가 15로 시작하게 되면 뒤는 3의 배수이면서 자리가 n-2번쨰 자리를 만족하기만 하면 되므로 이는 DP[n-2]와 동치이다. 맨 앞자리가 51로 시작해도 마찬가지이다. 계속해서 수형도를 그려나가면서 가질 수 있는 경우의 수를 전..

처음에 접근한 방식은 다음과 같다. # 처음에 접근한 방법 일단 문제를 이해하면 전체 트리의 부분 트리 중 원소의 갯수가 K인 것의 갯수를 구하라는 것과 동치라는 사실을 쉽게 이해할 수 있다. 또한 트리라는 것을 감안할 때 DFS를 이용하여 루트가 밑쪽에 위치한 트리의 원소의 갯수를 활용하여 루트가 위쪽에 위치한 트리의 원소의 갯수를 도출시킬 수 있다는 사실을 파악하였다. 따라서 이러한 속성을 활용하여 dp[i][j]를 i를 Root node로 하고 해당 트리에 속한 원소의 갯수가 j를 만족하는 갯수라고 설정하였다. 이를 바탕으로 DFS를 타고 위로 올라가면서 점화식을 도출하려고 시도하였다. 다만 이 방법의 문제는 점화식을 세우는 것에 무리가 많다는 점이다. dp[i][j]를 구하기 위해서는 i 노드의 ..