11726

https://www.acmicpc.net/status?user_id=starkshn&problem_id=11726&from_mine=1

배운 부분

문제를 일단 잘 읽자!

10007로 나누어서 출력하라는 부분 간과한점이랑 DP문제인점을 처음에 간과한점..

반복되는 부분에서의 캐시 활용을 기억을 하자...

#include <iostream>
#include <cstring>
using namespace std;

int cache_S[1001];

int Square(int num)
{
	// 기저
	if (num <= 1) return 1;

	// 캐시
	int& ret = cache_S[num];
	if (ret != -1) return ret;

	// 구하기
	return ret = (Square(num - 1) + Square(num - 2)) % 10007;
}

#pragma endregion

int main()
{
	memset(cache_S, -1, sizeof(cache_S));
	int num;
	cin >> num;
	int result = Square(num);
	cout << result;

	return 0;
}

나는 일단 이렇게 풀었는데 구글링해서 보면은 거의 대부분 아래 코드처럼 푼거같음.

#include <iostream>
#include <vector>

using namespace std;


int main() {

	int n; 
	cin >> n; 

	vector<int> dp;
	dp.push_back(1);
	dp.push_back(2);
	for (int i = 2; i < n; i++) {
		dp.push_back((dp[i - 1] + dp[i - 2])%10007);
	}
	cout << dp[n - 1] ;
	
	return 0;
}

이것도 신박? 한득하면서도 엄청좋은 코드인거같다...

11727

https://www.acmicpc.net/problem/11727

똑같은 문제임.

#include <iostream>
#include <cstring>
using namespace std;
int cache_11727[1001];

int S_11727(int num)
{
	// 기저
	if (num <= 1) return 1;

	// 캐시
	int& ret = cache_11727[num];
	if (ret != -1) return ret;

	// 구하기
	return ret = ( (S_11727(num - 1) + S_11727(num - 2) + S_11727(num - 2))) % 10007;
}

int main()
{
	memset(cache_11727, -1, sizeof(cache_11727));
	int num;
	cin >> num;
	int result = S_11727(num);
	cout << result;

	return 0;
}

바뀐거는

Squar(num -2)를 두번 호출한 부분임.

이렇게 시작하는거랑

이렇게 시작하는거랑

이렇게 시작하는게 있기 때문이다.