[BOJ][DP][실3][9095] 1,2,3 더하기

문제 링크

1,2,3 더하기/실3

첫 번째 풀이 : 다이나믹 프로그래밍, Top-Down

알고리즘

어떤 수를 만들기 위해서 마지막에 더해지는 수는 1,2,3 중에 하나여야합니다.

dp[i] = i번째 수를 1,2,3으로 표현하는 방법의 수

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 12

int dp[MAX];

using namespace std;

int main(void) {
  //freopen("input.txt", "r", stdin);

  int n = 0;
  cin >> n;

  for (int i = 0; i < n; i++) {
    int  m = 0;
    cin >> m;
    memset(dp, MAX, 0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    
    for (int j = 4; j <= m; j++) {
      dp[j] = dp[j - 1];
      dp[j] += dp[j - 2];
      dp[j] += dp[j - 3];
    }

    cout << dp[m] << '\n';
  }

  return 0;
}

두 번째 풀이 : 다이나믹 프로그래밍, Bottom-Up

알고리즘

dp[i] = i번째 수를 1,2,3으로 표현하는 방법의 수

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 12

int dp[MAX];

using namespace std;

int foo(int m) {
  if (m == 1) return 1;
  else if (m == 2) return 2;
  else if (m == 3) return 4;
  else if (dp[m] > 0) return dp[m];
  else return dp[m] = foo(m - 1) + foo(m - 2) + foo(m - 3);
}

int main(void) {
  //freopen("input.txt", "r", stdin);

  int n = 0;
  cin >> n;

  for (int i = 0; i < n; i++) {
    int m = 0;
    cin >> m;
    //memset(dp, MAX, 0);
    cout << foo(m) << '\n';
  }

  return 0;
}

결론

Success Notice: 다이나믹 프로그래밍의 쉬운 문제를 top-down, bottom-up 두 가지 방법으로 풀어봤습니다. 두 가지 모두 i에 대한 반복문에서 dp[i]를 구한다는 공통점이 있습니다. 수고하셨습니다.