ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 15988 1, 2, 3 더하기 3 (C++)

Posted on Mar 4, 2021 #동적프로그래밍(DP)   #Algorithm  

15988 | 1, 2, 3 더하기 3

🙋‍♀️ 문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

🙌 입출력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

🙋‍♂️ 예제 입출력

3
4
7
10

7
44
274

🚀 코드

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;

vector<long long> dpTable(1000001);

void dp(int n) {
	dpTable[0] = 0;
	dpTable[1] = 1;
	dpTable[2] = 2;
	dpTable[3] = 4;
	long long d = 1000000009;

	for (int i = 4; i <= n; i++) {
		dpTable[i] = dpTable[i - 1] + dpTable[i - 2] + dpTable[i - 3];
		dpTable[i] %= d;
	}

	cout << dpTable[n] << '\n';
	return;
}


int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t = 0;
	int n = 0;

	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		dp(n);
	}
	return 0;
}

🌠 메모

이 문제는 [백준] 9095 1, 2, 3 더하기 문제와 동일한 알고리즘을 통해 풀 수 있다. 점화식에 대한 설명이 필요하다면 이전 포스팅을 참고하자.

문제를 풀고 나서 신경써야 할 부분은 오버플로우인데, 이게 눈으로 직접 확인하기가 어려운 부분이다보니 고치는데 시간이 좀 걸렸다.

정확한 이유는 모르겠다만, 나누기 전의 값들을 한번에 더하고, 그 다음 값을 나눠주니 정답처리가 되었다..



# 카테고리