백준 9095번 : 1, 2, 3 더하기 C++

https://www.acmicpc.net/problem/9095

 

 

문제 탐색

입력 : n

0<n<11

 

필요한 식

1. 배열 초기화

dp[0] = 1;
dp[1] = 2;
dp[2] = 4;

for(int i = 3; i < 11; i++){
   dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}

사실 시간 복잡도는 고려 안해도 될 정도..의 숫자라서~

미리 123 조합을 구해뒀습니다

한 5까지의 조합을 구해보니 규칙이 나오더라고요!!!

 

2. 케이스 입력

 1) 테스트 케이스 수 입력 = t

 2) 구하고 싶은 숫자 입력 * t

 3) 해당 수의 조합 출력

 

그래서 순서를

1) 배열 초기화

2) 테스트 케이스 입력

3) 구하고 싶은 숫자 입력 반복문

4) 조합의 수 출력 반복문

이렇게 구성했습니다.

 

최종 코드

#include <iostream>

using namespace std;

int dp[11];

int main(){
  dp[0] = 1;
  dp[1] = 2;
  dp[2] = 4;

  for(int i = 3; i < 11; i++){
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
  }

  int t;
  cin >> t;

  int test[t];

  for(int i = 0; i < t; i++){
    cin >> test[i];
  }

  for(int i = 0; i<t;i++){
    cout << dp[test[i]-1]<< "\n";
  }
  
  return 0;
}

이렇게 됩니다~~!!!