[C++] 백준 9095번 - 다이나믹 프로그래밍

문제 접근

 

위 그림은 n이 각각 3, 4, 5일 때 가능한 모든 경우를 나열한 거예요. 훑어서 살펴보면 어떤 규칙이 있는 느낌이 들어요.

 

2가 생기는 경우, 3이 생기는 경우를 경계로 비슷한 작업을 반복한다는 인상을 받으셨을 거라고 생각해요.

 

따라서 dp[n]을 n이 가질 수 있는 경우의 수라고 할 때, 우리는 점화식을 유도해서 문제를 해결할 수 있을 거예요. 이런 접근법을 다이나믹 프로그래밍이라고 해요.

 

 

그러면 앞선 n값도 살펴봐요. n=1부터 경우의 수가 1, 2, 4, 7, 13, ...으로 커지고 있네요.

 

여기서 우리는 하나의 규칙을 확인할 수 있어요. 7 = 1 + 2 + 4이고, 13 = 2 + 4 + 7이네요!

 

그러면 n의 결과값은 앞선 세 가지 경우의 수를 모두 더해서 나온 값이 되겠어요.

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

코드

#include <iostream>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  
  int T, n;
  int arr[11];
  
  arr[1] = 1; arr[2] = 2; arr[3] = 4;
  for (int i = 4; i < 11; i++) {
    arr[i] = arr[i-3] + arr[i-2] + arr[i-1];
  }
  
  cin >> T;
  for (int i = 0; i < T; i++) {
    cin >> n;
    cout << arr[n] << '\n';
  }
  return 0;
}