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

문제 링크: https://www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

1. 주의할 점

- DP로 풀 경우 끝에 어떤 숫자가 왔는지 기억해야 한다. 여기서는 1,2,3 총 3개의 숫자를 사용하므로 결과적으로 10000 X3짜리 배열을 사용하면 된다.

- DP를 사용하지 않고 단순계산을 해도 시간초과가 나지 않는다(단, 특정 조건 하에 수행해야 한다)

 

2. 구현

- 전체를 블록으로 생각하고 입력받은 수를 3으로 나눴을 경우 3이 최대 몇개 있을수 있는지 구한다.

  [0, 입력받은 수/3] 까지 for문을 돌려서 입력받은 수 - 크기 3짜리 블록이 차지하는 공간에 1과 2를 이용해서 채울 수      있는 모든 경우의 수를 구한다. 

  위의 경우의 수 또한 남은 공간/2 로 나눴을 때 몫+1을 하면 답이 도출된다. 이때, 도출되는 답들의 합을 구하면 최종      답에 도달한다.

 

#include <iostream>
using namespace std;

int main() {
	int num, test;
	long long result;
	cin >> test;
	for (int t = 0; t < test; t++) {
		cin >> num;
		result = 0;
		int q = num / 3, remain;
		for (int i = 0; i <= q; i++) {
			remain = num - 3 * i;
			result += ((remain / 2) + 1);
		}
		cout << result << '\n';
	}
	system("pause");
	return 0;
}