[백준 9095] 1,2,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, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1

3 4 7 10

예제 출력 1

7 44 274

1. 다이나믹 프로그래밍 기법

n을 만들기 위해서 1,2,3만 사용하기 때문에

dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 임을 금방 알 수 있다.

이를 bottom-up으로 반복 해주면 끝.

#include<iostream>
#define size 11
 
using namespace std;
 
int main(){
    int t, n;
    int *dp = new int[size];
    
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 4; i <= n; i++)
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        cout<<dp[n]<<endl;
    }
}

2. 다중 for문 기법

무식하게, for 반복문을 사용하여 돌린다.

for(int l1 = 1; l1 <= 3; l1++){

    //if로 무식하게 검사

    for(int l2 = 1; l2 <= 3; l2++){

     // if로 검사(n == l1 + l2)??

    }

.....

}

#include<iostream>
 
using namespace std;
 
int main(){
    int t;
    cin >> t;
    
    while(t--){
        int ans = 0;
        int n;
        cin >> n;
        for(int l1 = 1; l1 <= 3; l1++){
            if(l1 == n)
                ans++;
            for(int l2 = 1; l2 <= 3; l2++){
                if(l1+l2 == n)
                    ans++;
                for(int l3 = 1; l3 <= 3; l3++){
                    if(l1+l2+l3 == n)
                        ans++;
                    for(int l4 = 1; l4 <= 3; l4++){
                        if(l1+l2+l3+l4 == n)
                            ans++;
                        for(int l5 = 1; l5 <= 3; l5++){
                            if(l1+l2+l3+l4+l5 == n)
                                ans++;
                            for(int l6 = 1; l6 <= 3; l6++){
                                if(l1+l2+l3+l4+l5+l6 == n)
                                    ans++;
                                for(int l7 = 1; l7 <= 3; l7++){
                                    if(l1+l2+l3+l4+l5+l6+l7 == n)
                                        ans++;
                                    for(int l8 = 1; l8 <= 3; l8++){
                                        if(l1+l2+l3+l4+l5+l6+l7+l8 == n)
                                            ans++;
                                        for(int l9 = 1; l9 <= 3; l9++){
                                            if(l1+l2+l3+l4+l5+l6+l7+l8+l9 == n)
                                                ans++;
                                            for(int l10 = 1; l10 < 3; l10++){
                                                if(l1+l2+l3+l4+l5+l6+l7+l8+l9+l10 == n)
                                                    ans++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;    
}

3. 재귀 호출

 차례대로 얼마나 더했는지 확인하는 sum 변수와

 목표값인 goal 변수를 지속적으로 확인한다.

#include<iostream>
 
using namespace std;
 
int go(int sum, int goal){
    if(sum > goal)
        return 0;
    if(sum == goal)
        return 1;
    int now = 0;                    // 1,2,3으로 goal을 만들 수 있는 방법 
    for(int i = 1; i <= 3; i++)
        now += go(sum + i, goal);
    return now;
}
int main(void){
    int t;
    cin >> t;                    // test case
    while(t--){
        int sum = 0, goal;                
        cin >> goal;                // 만들어야 하는 숫자 
        cout << go(sum, goal) << '\n';        // 재귀연산 호출 
    }
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.