[c/c++] 백준 9095(Silver 3)

🔨 문제

https://www.acmicpc.net/problem/9095
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1
  정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

🔨 해결방법

해당 문제는 n=1일 때 1, n=2일 때 2, n=3일 때 4의 결과값을 가진다. 이를 활용하여 n=4일 때도 구할 수 있기 때문에 다이나믹 프로그래밍을 이용하여 문제를 해결하였다.

다이나믹 프로그래밍이란 큰 문제를 작은 부분 문제로 나누어 해결하는 방법이다. 중복되는 계산을 피하기 위해 작은 문제들의 해를 기억하고 활용하여 전체 문제를 효율적으로 해결할 수 있다.

int dp[11]={1,2,4};

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

이 문제는 주어진 n값의 앞서 구하여 저장한 n-1, n-2, n-3의 값을 더하여 구할 수 있다.

🔨 코드

#include <iostream>
using namespace std;

int Count(int n){
    int dp[11]={1,2,4};

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

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t=0, num=0;
    cin >> t;

    for(int i=0;i<t;i++){
        cin >> num;
        int result=Count(num);
        cout << result << '\n';
    }


    return 0;
}