#15988: 1, 2, 3 더하기 3

백준 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보다 작거나 같다.

풀이:

• 이 문제는 #9095: 1, 2, 3 더하기 문제와 푸는 방식이 완전 동일하다. 따라서 풀이 법은 #9095: 1, 2, 3 더하기을 참고하기 바란다.
• #9095: 1, 2, 3 더하기와의 차이점은 n의 최대값이 1,000,000까지 늘어났다는 것이다. 출력에 1,000,000,009로 나눈 나머지를 출력하라는 조건도 추가 되었다. 따라서, d 배열에 값을 저장할 때마다 나머지를 저장 해주도록 한다. 추가로 n의 값이 커짐에 따라서 배열에 저장 되는 값의 최대 크기가 늘어났고 1,000,000,009의 나머지를 저장하라는 것은 저장 되는 값이 1,000,000,009보다 커진다는 뜻이기 때문에 int가 아닌 long long 자료형으로 배열을 만들어 주도록 한다.

코드:

#include <iostream>

using namespace std;

//저장 되는 최대값이 int로는 부족하므로 long long으로 선언 
long long d[1000001] = {1, 1, 2}; //배열이 0, 1, 2인 경우의 초기값 설정

int main(){
	//입력
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		int temp;
		cin >> temp;
		for(int j = 3; j <= temp; j++){
			//전의 값은 1을 더해주고 전전의 값은 2를 더해주고 전전전의 값은 3을 더해주면 j가 나온다
			d[j] = (d[j-1]+d[j-2]+d[j-3])%1000000009; 
		}
		//출력
		cout << d[temp] << '\n';
	}
}