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

 

🤔 문제

 

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

 

---

👀 접근 방식

문제를 보자마다 dp로 해결해야 겠다고 생각해 아래와 같이 접근하였다

1. 1~1000000에 해당하는 dp값을 미리 구한다
2. 숫자 n이 입력되면 n번쨰 dp값을 출력한다.

처음에 어떻게 dp를 초기화 시킬지 감이 안와 1~6까지 직접 구해 패턴을 보려고 하였다.

 

dp[1] -> 1

dp[2] -> 2

dp[3] -> 4

dp[4] -> 7

dp[5] -> 13

dp[6] -> 24

 

이를 통해 4이상부터는 1~3단계 이전의 dp값을 모두 더한 값이 해당 dp값이라는 것을 알게 되어 아래와 같이 식을 만들 수 있었다.

 

dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] + dp[ i - 3 ] , ( i가 4 이상일때 ) 

 

바로 구현하여 제출하였는데, 틀렸다고 나와 문제를 다시 보니 출력부분에 "1,000,000,009로 나눈 나머지를 출력" 이라고 명시 돼있어 아래와 같이 수정하였다.

 

dp[ i ] = ( dp[ i - 1 ] + dp[ i - 2 ] + dp[ i - 3 ] ) % 1000000009, ( i가 4 이상일때 ) 

 

다행이 바로 성공할 수 있었다. 문제를 꼼꼼히 봐야했는데 ㅎ

---

💻 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include<cstring>

#define ull unsigned long long

using namespace std;

int t;
ull dp[1000001];

unsigned long long func(int num)
{
	// 현재 값이 음수면 0 리턴
	if (num < 0)
		return 0;

	// 현재 값에 해당하는 dp가 있으면 dp 리턴
	if (dp[num])
	{
		return dp[num];
	}
	// 현재 값에 해당하는 dp가 없으면 1,2,3 을 뺀값을 재귀함수 호출
	// +) 호출한 값을 1000000009로 나눈 나머지를 현재 dp에 저장 후 리턴
	else {
		dp[num] = ( func(num - 1) + func(num - 2) + func(num - 3) ) % 1000000009;
		return dp[num];
	}
		


}

int main()
{
	// dp 초기화
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	// 3~1000000 까지의 dp를 미리 채움
	for (int i = 3; i <= 1000000; ++i)
	{
		func(i);
	}

	// 테스트 케이스 입력
	cin >> t;

	// 입력값에 해당하는 dp값 출력
	while (t--)
	{
		int input; cin >> input;

		cout << dp[input]  << '\n';
	}
}