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

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

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

9095번: 1, 2, 3 더하기

 

● 알아야 할 것

: DP 문제집에 있는 문제 

https://pirateturtle.tistory.com/202

 

● 풀이 과정

: 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;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [500 - 브루트 포스] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	2309	일곱 난쟁이	https://pirateturtle.tistory.com/228
2	3085	사탕 게임	https://pirateturtle.tistory.com/229
3	1476	날짜 계산	https://pirateturtle.tistory.com/230
4	1107	리모컨	https://pirateturtle.tistory.com/231
5	14500	테트로미노	https://pirateturtle.tistory.com/232
6	6064	카잉 달력	https://pirateturtle.tistory.com/233
7	1748	수 이어 쓰기 1	https://pirateturtle.tistory.com/234
8	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/235