[백준] 1, 2, 3 더하기 3

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

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
//#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector<long long> table(1000001);
	table[1] = 1; // 1
	table[2] = 2; // 2, 1+1
	table[3] = 4; // 3, 2+1, 1+2, 1+1+1
	for (int i = 4; i < 1000001; i++) {
		table[i] = (table[i - 1] + table[i - 2] + table[i - 3]) % 1000000009;
	}

	int t;
	cin >> t;
	while (t-- > 0) {
		int n;
		cin >> n;

		cout << table[n] % 1000000009 << "\n";
	}

	return 0;
}

 

문제에서 1000000009 로 나누라고 했는데 제대로 안 읽고 풀어서 빼먹었다.. 제발 문제 풀 때 정신 좀 차려라.