[Dynamic Programming] 백준 9095번 “1, 2, 3 더하기” C++ 풀이

문제 링크

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

풀이

• 해당 문제는 규칙을 찾는 것이 중요합니다.

• 따라서, 아래 그림을 통해 규칙을 찾아보겠습니다.

  

  • 우선, 4 를 만들 수 있는 조합은 7가지로 이루어져있습니다.
    • 1 + 로 시작하는 조합
      • 1 + 1 + 1 + 1
      • 1 + 1 + 2
      • 1 + 2 + 1
      • 1 + 3
    • 2 + 로 시작하는 조합
      • 2 + 1 + 1
      • 2 + 2
    • 3 + 로 시작하는 조합
      • 3 + 1
  • 즉, 1 + 로 시작하는 조합의 개수는 4 개입니다.
    • 이는, 3 을 만들 수 있는 조합의 개수와 동일합니다.
  • 또한, 2 + 로 시작하는 조합의 개수는 2 개입니다.
    • 이는, 2 를 만들 수 있는 조합의 개수와 동일합니다.
  • 마지막으로, 3 + 로 시작하는 조합의 개수는 1 개입니다.
    • 이는, 1 를 만들 수 있는 조합의 개수와 동일합니다.

• 따라서, 4 를 만들 수 있는 조합은, 아래 식을 통해 계산할 수 있습니다.

  • 3 을 만들 수 있는 조합의 개수 + 2 를 만들 수 있는 조합의 개수 + 1 을 만들 수 있는 조합의 개수

• 따라서, 해당 문제는 아래 점화식을 통해 해결할 수 있습니다.

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

코드

#include <iostream>
#include <vector>

using namespace std;

// 1 ~ n 까지, 각 정수가 몇 개의 조합으로 이루어져있는지를 저장해놓는 변수
vector<int> case_number;

// 입력 받은 n 이, 몇 개의 조합으로 이루어져있는지를 출력
int dp(int n){

    // 4 ~ n 까지, 각 정수가 몇 개의 조합으로 이루어져있는지, 차례대로 계산
    for (int i=4; i<=n; ++i){
        int new_case = case_number[i-3] + case_number[i-2] + case_number[i-1];
        case_number.push_back(new_case);
    }
    // 입력 받은 n 이, 몇 개의 조합으로 이루어져있는지 출력
    return case_number[n];
}

int main(){

    // 테스트 케이스 개수
    int test_case;
    cin >> test_case;

    for (int i=0; i<test_case; ++i){

        // 각 테스트 케이스
        int n;
        cin >> n;

        // 0 ~ 3 까지, 각 정수가 몇 개의 조합으로 이루어져있는지를 초기값으로 저장
        case_number = {0, 1, 2, 4};

        // 입력 받은 정수가 3 이하라면, 이미 계산되어있는 초기값을 배열에서 반환
        if (n <= 3){
            cout << case_number[n] << endl;
        }
        // 입력 받은 정수가 3 초과라면, 해당 정수를 만들 수 있는 조합을 계산
        else{
            cout << dp(n) << endl;
        }
    }
}

참고

• https://sanghyu.tistory.com/108
• https://blog.naver.com/PostView.nhn?blogId=vjhh0712v&logNo=221470862600