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

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

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

15990번: 1, 2, 3 더하기 5

 

● 알아야 할 것

: 다이나믹 프로그래밍

: vector 자료구조와 메소드

 

● 풀이 과정

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

1. 테이블 정의하기

→ end1 : index를 만드는데 마지막으로 추가한 숫자가 1인 경우

→ end2 : index를 만드는데 마지막으로 추가한 숫자가 2인 경우

→ end3 : index를 만드는데 마지막으로 추가한 숫자가 3인 경우

 

2. 점화식 찾기

→ end1[index] = end2[index - 1] + end3[index - 1]

→ end2[index] = end1[index - 2] + end3[index - 2]

→ end3[index] = end1[index - 3] + end2[index - 3]

각 index를 만드는데 1, 2, 3의 합으로 나타내는 방법의 수

dp[index] = end1[index] + end2[index] + end3[index]

 

3. 초기값 정하기

→ (index) 1을 표현하는 1, 2, 3의 합으로 나타내는 방법 : 1

→ (index) 2을 표현하는 1, 2, 3의 합으로 나타내는 방법 : 2

→ (index) 3을 표현하는 1, 2, 3의 합으로 나타내는 방법 : 2 + 1 / 1 + 2 / 3

 

● 주의 할 것

: 점화식을 처음 찾을 때 dp[index - 1] - end1[index - 1] 과 같이 계산하여 구했는데

이는 모듈러 연산 후 뺄셈 연산을 하게 되면 계산과정에 오차가 생겨 오답이 나온다.

따라서 모듈러 연산과 덧셈 연산을 같이하여 오류가 안나도록 한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// dp : 1, 2, 3의 합으로 나타내는 방법의 수
// end1 : 마지막 숫자가 1인 경우
// end2 : 마지막 숫자가 2인 경우
// end3 : 마지막 숫자가 3인 경우
vector<long long> dp, end1, end2, end3;
int T, N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> T;
    
    dp.assign(100000 + 1, 0);
    end1.assign(100000 + 1, 0);
    end2.assign(100000 + 1, 0);
    end3.assign(100000 + 1, 0);
    
    // 초기값 설정
    dp[1] = 1;
    end1[1] = 1;
 
    dp[2] = 1;
    end2[2] = 1;

    dp[3] = 3;
    end1[3] = 1;
    end2[3] = 1;
    end3[3] = 1;

    // Bottom - Up
    for(int i = 4; i <= 100000; i++)
    {
        // 주석과 같이 작성하면 오답 결과 (원인 : 모듈러 연산 후 뺄셈)
        // end1[i] = dp[i - 1] - end1[i - 1];
        // end2[i] = dp[i - 2] - end2[i - 2];
        // end3[i] = dp[i - 3] - end3[i - 3];
        end1[i] = (end2[i - 1] + end3[i - 1]) % 1000000009;
        end2[i] = (end1[i - 2] + end3[i - 2]) % 1000000009;
        end3[i] = (end1[i - 3] + end2[i - 3]) % 1000000009;
        dp[i] = (end1[i] + end2[i] + end3[i]) % 1000000009;
    }
    
    for(int t = 0; t < T; t++)
    {
        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