알고리즘 - 다이나믹 프로그래밍

1_DP.md

다이나믹 프로그래밍

여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

DP를 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

2_boj1463.cpp

#include <bits/stdc++.h>
using namespace std;

int N, cached[1000005];

int f(int n) {
  if (n == 1) return 0;
  if (cached[n] != 0)  return cached[n];
  
  int res = f(n - 1) + 1;
  if (n % 3 == 0) res = min(res, f(n/3) + 1);
  if (n % 2 == 0) res = min(res, f(n/2) + 1);
  cached[n] = res;
  return res;
}
  
int main() {
  scanf("%d", &N);
  printf("%d", f(N));
}

2_boj1463_1.cpp

#include <bits/stdc++.h>
using namespace std;

int N, cached[1000005];
  
int main() {
  scanf("%d", &N);
  cached[2] = 1;
  for (int i = 2; i <= N; ++i) {
    cached[i] = cached[i - 1] + 1;
    if (i % 3 == 0) 
      cached[i] = min(cached[i/3] + 1, cached[i]);
    if (i % 2 == 0)
      cached[i] = min(cached[i/2] + 1, cached[i]);
  }
  printf("%d", cached[N]);
}

3_boj2579.cpp

#include <bits/stdc++.h>
using namespace std;

const int STEPS = 2;
int cache[305][STEPS];
int scores[305];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  
  for (int i = 1; i <= n; ++i) cin >> scores[i];
  cache[1][0] = cache[1][1] = scores[1];
  cache[2][0] = scores[1] + scores[2], cache[2][1] = scores[2];
  for (int i = 3; i <= n; ++i) {
    cache[i][0] = scores[i] + cache[i-1][1];
    cache[i][1] = scores[i] + max(cache[i-2][0], cache[i-2][1]);
  }
  cout << max(cache[n][0], cache[n][1]) << '\n';
}

3_boj9095.cpp

#include <bits/stdc++.h>
using namespace std;

int cache[15];
int f(int n) {
  if (cache[n]) return cache[n];
  return f(n - 1) + f(n - 2) + f(n - 3);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t, n;
  cin >> t;
  cache[1] = 1, cache[2] = 2, cache[3] = 4;
  while (t--) {
    cin >> n;
    cout << f(n) << '\n';
  }
}
  
  

4_boj2579.cpp

#include <bits/stdc++.h>
using namespace std;

const int STEPS = 2;
int scores[305];
int cache[305][STEPS];
  // cache[i][j]는 
  // j=0, i번째 계단을 밟았을때 연속 아니고 그때 가능한 최대값
  // j=1, i번째 계단을 밟았을때 2개 연속이고 그때 가능한 최대값

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  for(int i = 1; i <= n; ++i) cin >> scores[i];
  
  cache[1][0] = scores[1];
  cache[2][0] = scores[2], cache[2][1] = scores[1] + scores[2];
  for (int i = 3; i <= n; ++i) {
    cache[i][0] = scores[i] + max(cache[i-2][0], cache[i-2][1]);
    cache[i][1] = scores[i] + cache[i-1][0];
  }
  cout << max(cache[n][0], cache[n][1]) << '\n';
}