[C++] 백준 9095번 1,2,3 더하기

 

 

정수 n이 주어졌을 때, 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제입니다.

 

여러번의 반복 작업이 있을때 유용하게 만들었다. 다이나믹 프로그래밍 기법으로 메모이제이션을 사용했습니다.

 

이 문제의 규칙은

1을 만드는 방법은 1가지

2를 만드는 방법은 2가지

3을 만드는 방법은 4가지

 

4를 만드는 방법은 1 + 2 + 4 = 7가지

5를 만드는 방법은 2 + 4 + 7 = 13가지

 

규칙은 현재 찾는 값이 5라면

2를 만드는 방법  =  2가지

3를 만드는 방법  =  4가지

4를 만드는 방법  =  7가지

2 + 4 + 7 = 13

5를 만드는 방법 = 13이 된다.

 

그렇기 때문에 x라는 값을 구하게 될때

x-1, x-2, x-3의 값이 있다면 편리하게 구할 수 있습니다.

 

전역변수로 memo[]에 코드가 실행되면서 찾은 값들이 입력이 됩니다..

그리고 새로 찾는 숫자가 memo[]에 있는 숫자라면 여러 연산없이 풀 수 있습니다.

 

#include <iostream>
using namespace std;

int memo[100] = {0,};
int memonum = 3;

int main(int argc, char *argv[])
{
	int cycle = 0;
	int num;
	int tmp;
	int x[3] = { 1, 2, 4 };
	memo[0] = 0;
	memo[1] = 1;
	memo[2] = 2;
	memo[3] = 4;
	
	cin >> cycle;

	for (int i = 0; i < cycle; ++i) {
		cin >> num;
		if (num > memonum) {
			x[0] = memo[memonum - 2];
			x[1] = memo[memonum - 1];
			x[2] = memo[memonum];
		}
		else {
			cout << memo[num] << endl;
			continue;
		}
		while (num > memonum) {
			++memonum;
			memo[memonum] = x[0] + x[1] + x[2];
			x[0] = memo[memonum - 2];
			x[1] = memo[memonum - 1];
			x[2] = memo[memonum];
		}
		cout << memo[memonum] << endl;
	}
	return 0;
}