[DP] 백준 문제 풀이 - 15990 1,2,3 더하기 5

👩🏻‍💻 문제링크

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

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

 

✍️ 아이디어

1. 1,2,3의 합 1과 같이 result[i-3] + result[i-2] + result[i-1] 에 i-1에서 마지막이 1인거, i-2에서 마지막이 2인거, i-3에서 마지막이 3인것을 빼줘야 한다고 생각은 함.

2. 하지만 어뜨케 구현해야할지 생각을 못함(2차원배열을 어케 생각해;;)

 

3. 예외 처리로 [1], [2], [3]에 해당하는 배열을 초기화 하였다

✍️소스코드

• 나의 풀이

#include <iostream>	
using namespace std;
long long result[100001][4]; //마지막에 더한값이 1,2,3인 경우를 나누어 주었다

int main()
{
	int T; cin>>T;
	result[1][1]=1;
	result[2][2]=1;
	result[3][1]=1,result[3][2]=1,result[3][3]=1;
	for(int i=0; i<T; i++)
	{
		int n; cin>>n;
		for(int j=4; j<=n; j++)
		{
			result[j][1]=((result[j-1][2]) + (result[j-1][3]))%1000000009;
			result[j][2]=((result[j-2][1]) + (result[j-2][3]))%1000000009;
			result[j][3]=((result[j-3][1]) + (result[j-3][2]))%1000000009;
		}
		cout<< (result[n][1]+result[n][2]+result[n][3]) % 1000000009 <<'\n';
	}
}

 

 

체감난이도	걸린시간	참고	사용 문법
상	1hour	이차원 배열로 메모를 구현해야한다는것 (백준 강의)	2차원 DP

 

 

<남의 풀이>  (예외처리를 조금 더 우아하게 했지만 굳이..?)

#include <stdio.h>
long long d[1000001][4];
const long long mod = 1000000009LL;
const int limit = 100000;
int main() {
    for (int i=1; i<=limit; i++) {
        if (i-1 >= 0) {
            d[i][1] = d[i-1][2] + d[i-1][3];
            if (i == 1) {
                d[i][1] = 1;
            }
        }
        if (i-2 >= 0) {
            d[i][2] = d[i-2][1] + d[i-2][3];
            if (i == 2) {
                d[i][2] = 1;
            }
        }
        if (i-3 >= 0) {
            d[i][3] = d[i-3][1] + d[i-3][2];
            if (i == 3) {
                d[i][3] = 1;
            }
        }
        d[i][1] %= mod;
        d[i][2] %= mod;
        d[i][3] %= mod;
    }
    int t;
    scanf("%d",&t);
    while (t--) {
        int n;
        scanf("%d",&n);
        printf("%lld\n",(d[n][1] + d[n][2] + d[n][3])%mod);
    }
}