문제 풀이

숫자의 합이 1로 끝나는 경우의수, 2로 끝나는 경우의 수, 3으로 끝나는 경우의 수를 저장하기 위한 2차원 배열을 사용한다.
d[i][j] = i의 숫자를 만들기 위한 j로 끝나는 숫자의 경우의 수라고 생각한다.

d[1][1] = 1 -> 1개
d[2][1] = (1 + 1) -> 1개
d[2][2] = 2 -> 1개
d[3][1] = (1 + 1 + 1) -> 1개
d[3][2] = (1 + 2) -> 1개
d[3][3] = 3 -> 1개

중복을 제거하기 위해 1로 끝나는 경우는 1로 끝나는 경우의 수만 고려하고
2로 끝나는 경우는 1과 2로 끝나는 경우의 수만 고려하고
3으로 끝나는 경우는 1, 2, 3 모두 고려한다.

예를 들어 4를 만드는 방법 수를 찾을때는 d[1][1] + d[2][1] + d[2][2] +d[3][1] + d[3][2] + d[3][3]을 해야 된다.
이렇게 오름차순으로 고려하지 않는다면 다음과 같은 중복 문제가 생긴다.

n = 4
d[1][1] 에서 3을 더하는 경우 -> 1 + 3
d[3][3] 에서 1을 더하는 경우 -> 3 + 1 (중복)

또 다른 예로
n = 5
d[2][2] 에서 3을 더하는 경우 -> 2 + 3
d[3][3] 에서 2를 더하는 경우 -> 3 + 2 (중복)

그러므로 모든 수식의 경우의 수는 오름차순으로 이루어지도록 고려해야한다.

문제 링크

boj/15989

소스코드

PS/15989.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<queue>
using namespace std;

int d[10001][4];
int main(void)
{
	int T;
	cin >> T;

	d[1][1] = 1;
	d[2][1] = 1;
	d[2][2] = 1;
	d[3][1] = 1;
	d[3][2] = 1;
	d[3][3] = 1;

	for (int i = 4; i <= 10000; i++)
	{
		d[i][1] = d[i - 1][1];
		d[i][2] = d[i - 2][1] + d[i - 2][2];
		d[i][3] = d[i - 3][1] + d[i - 3][2] + d[i - 3][3];
	}
	while (T--)
	{
		int n;
		cin >> n;
		cout << d[n][1] + d[n][2] + d[n][3] << '\n';
	}
}