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

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

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

15988번: 1, 2, 3 더하기 3

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

 

● 풀이 과정

: 기존 1, 2, 3 더하기 문제에서 크게 벗어나지 않았다.

 

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

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

 

2. 점화식 찾기

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

 

3. 초기값 정하기

dp[1] = 1

→ (1)

dp[2] = 2

→ (1+1) / (2)

dp[3] = 4

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

 

 

● 주의 할 것

: 각 index에 저장할 값 계산을 다하고 나머지 연산을 해야한다.

 

: dp의 자료형을 long long으로 선언해야 '틀렸습니다'를 받지 않는다.

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// dp[index] : 1, 2, 3의 합으로 index를 나타내는 방법의 수
long long dp[1000001];
int T, N;

void program()
{
    // 초기값 설정
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    
    // 점화식
    for(int index = 4; index <= 1000000; index++)
        dp[index] = (dp[index - 1] + dp[index - 2] + dp[index - 3]) % 1000000009;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> T;
    
    program();
    
    while(T--)
    {
        cin >> N;
        
        cout << dp[N] << "\n";
    }
    
    return 0;
}

 

 

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

번호	문제 번호	문제 이름	풀이 링크
1	15988	1, 2, 3 더하기 3	https://pirateturtle.tistory.com/214
2	1149	RGB거리	https://pirateturtle.tistory.com/215
3	1309	동물원	https://pirateturtle.tistory.com/216
4	11057	오르막 수	https://pirateturtle.tistory.com/217
5	9465	스티커	https://pirateturtle.tistory.com/218
6	2156	포도주 시식	https://pirateturtle.tistory.com/219
7	1932	정수 삼각형	https://pirateturtle.tistory.com/220
8	11055	가장 큰 증가 부분 수열	https://pirateturtle.tistory.com/221
9	11722	가장 긴 감소하는 부분 수열	https://pirateturtle.tistory.com/222
10	11054	가장 긴 바이토닉 부분 수열	https://pirateturtle.tistory.com/223
11	13398	연속합 2	https://pirateturtle.tistory.com/224
12	2133	타일 채우기	https://pirateturtle.tistory.com/225