[BOJ/백준] 9095 1, 2, 3 더하기

● [문제번호 9095] 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

● 알아야 할 것

: 다이나믹 프로그래밍

: vector 자료구조와 메소드

 

● 풀이 과정

: DP의 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ 각 index의 값은 1, 2, 3의 합으로 나타내는 방법의 수를 나타낸다.

 

2. 점화식 찾기

→ dp[index] = dp[index - 1] + dp[index - 2] + dp[index - 3]

 

dp[index]는 

dp[index - 1] 에서 구한 각 방법에 1을 추가하면 되는 것과

dp[index - 2] 에서 구한 각 방법에 2을 추가하면 되는 것과

dp[index - 3] 에서 구한 각 방법에 3을 추가하면 되는 것의 합이다.

 

3. 초기값 정하기

dp[1] = 1

→ (1)

dp[2] = 2

→ (1+1) / (2)

dp[3] = 4

→ (1+1+1) / (1+2) / (2+1) / (3)

 

● 주의 할 것

: 매 n값을 입력받을 때마다 DP를 실행하는 건 비효율적일 것 같았다.

그리고 n의 값이 최대 10까지 주어진다고 해서 미리 모든 케이스의 값을 구하였다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// DP의 테이블
vector<int> dp;
int T;

// DP 테이블 만드는 함수
void make_dp()
{
    // n은 최대 10개 이므로 11개의 할당 (0 index 사용은 선택적)
    dp.assign(11, 0);
    
    // 초기값
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    
    // 점화식으로 구한다
    for(int i = 4; i < 11; i++)
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 입력
    cin >> T;
    
    // DP 테이블 만드는 함수
    make_dp();
    
    // 구하고자하는 방법의 수를 바로 출력
    for(int t = 0; t < T; t++)
    {
        int n;
        cin >> n;
        
        cout << dp[n] << "\n";
    }

    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [400 - 다이나믹 프로그래밍 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1463	1로 만들기	https://pirateturtle.tistory.com/199
2	11726	2×n 타일링	https://pirateturtle.tistory.com/200
3	11727	2×n 타일링 2	https://pirateturtle.tistory.com/201
4	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/202
5	11052	카드 구매하기	https://pirateturtle.tistory.com/203
6	16194	카드 구매하기 2	https://pirateturtle.tistory.com/204
7	15990	1, 2, 3 더하기 5	https://pirateturtle.tistory.com/205
8	10844	쉬운 계단 수	https://pirateturtle.tistory.com/206
9	2193	이친수	https://pirateturtle.tistory.com/207
10	11053	가장 긴 증가하는 부분 수열	https://pirateturtle.tistory.com/208
11	14002	가장 긴 증가하는 부분 수열 4	https://pirateturtle.tistory.com/209
12	1912	연속합	https://pirateturtle.tistory.com/210
13	1699	제곱수의 합	https://pirateturtle.tistory.com/211
14	2225	합분해	https://pirateturtle.tistory.com/212