#1003

#include <iostream>
using namespace std;


int main()
{
	//todo
	//1. 0과 1의 count 되는 규칙찾기
	// 0은 2번째부터 피보나치 수열 적용되고, 1은 0부터 적용됨.

	int T, N;
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> N;

		int zero[41] = { 1, 0, };
		int one[41] = { 0,1, };

		for (int j = 2; j <= N; j++)
		{
			zero[j] = zero[j - 1] + zero[j - 2];
			one[j] = one[j - 1] + one[j - 2];
		}
		cout << zero[N] << " " << one[N] << "\n";
	}
}

#9184

#include <iostream>
using namespace std;

int arr[21][21][21] = { 0 };

int w(int a, int b, int c)
{
	if (a <= 0 || b <= 0 || c <= 0)
		return 1;

	else if (a > 20 || b > 20 || c > 20)
		return w(20, 20, 20);

	else if (arr[a][b][c] != 0) //이미 저장되어있는 값이라면 그 값을 return
		return arr[a][b][c];

	else if (a < b && b < c)
		arr[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);

	else
		arr[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);

	return arr[a][b][c];
}


int main()
{
	int a, b, c;

	while (1)
	{
		cin >> a >> b >> c;

		if (a == -1 && b == -1 && c == -1)
			break;

		cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
	}

	return 0;
}

#1904

//왜 15746으로 나누는지 궁금해서 찾아봤는데 별 의미 없다고 한다,,,

#include <iostream>
using namespace std;


int main()
{
	//todo
	//계산하다가 값이 넘어버리므로 계산중에 미리 %15746을 해주어야한다.
	int N;
	cin >> N;
	
	int* arr = new int[N + 1];
	arr[0] = 0; arr[1] = 1; arr[2] = 2;

	for (int i = 3; i <= N; i++)
	{
		arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
	}

	cout << arr[N];

	delete[] arr;

	return 0;
}

#9461

//long long 안써서 틀렸다..

#include <iostream>
using namespace std;

long long arr[101] = { 0, 1, 1, 1, 2, 2};

long long P(int n)
{
	if (n < 6)
		return arr[n];
	else
	{
		for (int i = 6; i <= n; i++)
		{
			arr[i] = arr[i - 1] + arr[i - 5];
		}
	}

	return arr[n];
}


int main()
{
	int T, N;
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> N;

		cout << P(N) << "\n";
	}

	return 0;
}

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;


int main()
{
	int N;
	int arr[1001][3] = { 0 }; //arr[i][0] = 빨간집 / arr[i][1] = 초록집 / arr[i][2] = 파랑집
	int cost[3] = { 0 };
	int min_ = 1001;
	
	cin >> N;

	arr[0][0] = 0; arr[0][1] = 0; arr[0][2] = 0;

	for (int i = 1; i <= N; i++)
	{
		cin >> cost[0] >> cost[1] >> cost[2];
		arr[i][0] = min(arr[i - 1][1], arr[i - 1][2]) + cost[0]; //현재 집이 빨간색일 때의 비용
		arr[i][1] = min(arr[i - 1][0], arr[i - 1][2]) + cost[1]; //현재 집이 초록색일 때의 비용
		arr[i][2] = min(arr[i - 1][0], arr[i - 1][1]) + cost[2]; //현재 집이 파란색일 때의 비용
	}

	min_ = min(arr[N][0], arr[N][1]);
	min_ = min(arr[N][2], min_);

	cout << min_ << "\n";
	return 0;
}

#1932

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
	int N, max_ = 0;
	int arr[500][500] = { 0 };

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0)
			{
				arr[i][j] = arr[i][j] + arr[i - 1][0];
				
			}
			else if (j == i)
			{
				arr[i][j] = arr[i][j] + arr[i - 1][j - 1];
			}
			else
			{
				arr[i][j] = arr[i][j] + max(arr[i - 1][j - 1], arr[i - 1][j]);
			}

			max_ = max(max_, arr[i][j]);
		}
	}

	cout << max_;
	return 0;
}

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
	int N;
	int arr[301] = { 0 };
	int dp[301] = { 0 };

	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}

	dp[1] = arr[1];
	dp[2] = max(arr[2], arr[2] + arr[1]); //한번에 2층으로 올라가는 것 vs 1층 + 2층
	dp[3] = max(arr[1] + arr[3], arr[2] + arr[3]);

	for (int i = 4; i <= N; i++)
	{
		dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]);
	}
	
	cout << dp[N];

	return 0;
}

#1463

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int N;
	cin >> N;

	vector<int> dp(N + 1);

	dp[0] = 0;
	dp[1] = 0;

	for(int i=2; i<=N; i++)
	{
		dp[i] = dp[i - 1] + 1;
		if ((i % 3)==0)
		{
			dp[i] = min(dp[i], dp[i / 3] + 1);
		}
		if ((i % 2) == 0)
		{
			dp[i] = min(dp[i], dp[i / 2] + 1);
		}
	}

	cout << dp[N];

	//delete[] dp;
	return 0;
}

#10844

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
	int N;
	int sum = 0;
	int arr[101][10] = { 0 };  //행에는 층수, 열에는 1~9까지 저장

	cin >> N;

	for (int i = 1; i < 10; i++)
		arr[1][i] = 1;

	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (j == 0)
				arr[i][j] = arr[i-1][j + 1];  // j=0일 때 앞,뒤는 1밖에 못옴
			else if (j == 9)
				arr[i][j] = arr[i-1][j - 1];  // j=9일 때 앞,뒤에는 8밖에 못옴
			else
				arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j + 1];

			arr[i][j] %= 1000000000;
			//나머지 계산을 해주는 이유는 type 범위를 초과해서 원치않는 값을 저장하기 때문
		}
	}

	for (int i = 0; i < 10; i++)
	{
		sum = (sum + arr[N][i]) % 1000000000;
	}

	cout << sum;
	return 0;
}

#2156

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
	//계단오르기 문제와 비슷하지만 조건이 하나 다름
	//계단오르기는 마지막 계단을 밟는 것이 필수이지만 이 문제는 필수가 아님
	//마지막 잔을 마시는 것 VS 마시지 않는 것 나누어서 case추가하고 max 비교 후 출력

	int N;
	int arr[10001] = { 0 };
	int dp[10001] = { 0 };

	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}

	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];

	for (int i = 3; i <= N; i++)
	{
		dp[i] = max(dp[i - 1], max(dp[i - 3] + arr[i] + arr[i - 1], arr[i] + dp[i - 2]));
	}

	cout << dp[N];

	return 0;
}

#2565

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int N, temp_x, temp_y, result=0;
	int dp[101] = { 0 };
	vector<pair<int, int>> vec;
	
	cin >> N;

	//처음에 (0,0) 넣어주기
	vec.push_back(make_pair(0, 0));

	for (int i = 0; i < N; i++)
	{
		cin >> temp_x >> temp_y;
		vec.push_back(make_pair(temp_x, temp_y));
	}

	sort(vec.begin(), vec.end());

	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (vec[i].second > vec[j].second)
			{
				if (dp[j] >= dp[i])
				{
					dp[i] = dp[j] + 1;
				}
			}
		}
		
		result = max(result, dp[i]);
	}

	//result의 값은 정렬된 가장 긴 값을 가지는 수열이므로
	//제거하려는 전깃줄의 값은 총 개수인 N에서 정렬된 result값을 빼면 된다.
	cout << N - result;
	return 0;
}

#11053

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
	int N, sum = 0;
	int arr[1001] = { 0 };
	int dp[1001] = { 1 };

	cin >> N;
	
	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}

	for (int i = 1; i <= N; i++)
	{
		dp[i] = 1;
		for (int j = 1; j < i; j++)
		{
			if (arr[i] > arr[j])
				dp[i] = max(dp[i], dp[j] + 1); //i 배열이 j 배열보다 크다면 1증가
		}
		sum = max(sum, dp[i]);
	}

	cout << sum;

	return 0;
}

#11054

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
	int N, result=0;
	int arr[1001] = { 0 };
	int dp_left[1001] = { 1 };
	int dp_right[1001] = { 1 };

	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	//왼쪽부터 증가하는 수열 찾기
	for (int i = 0; i < N; i++)
	{
		dp_left[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (arr[j] < arr[i] && dp_left[i] < dp_left[j] + 1)
			{
				dp_left[i] = dp_left[j] + 1;
			}
		}
	}
	
	//오른쪽부터 감소하는 수열 찾기
	for (int i = N-1; i >=0; i--)
	{
		dp_right[i] = 1;
		for (int j = N-1; j > i; j--)
		{
			if (arr[i] > arr[j] && dp_right[i] < dp_right[j] + 1)
			{
				dp_right[i] = dp_right[j] + 1;
			}
		}
	}

	for (int i = 0; i < N; i++) 
	{
		result = max(result, (dp_left[i] + dp_right[i]));
	}

	//중간의 수가 겹치므로 -1 해준다.
	cout << result - 1;

	return 0;
}

#9251

//이렇게 풀었는데 런타임 에러났다 ㄱ-

#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	string str1, str2;
	cin >> str1 >> str2;

	int x = str1.length();
	int y = str2.length();

	int** dp = new int*[x];

	for (int i = 0; i <= x; i++)
	{
		dp[i] = new int[y+1];
	}

	//dp초기화
	for (int i = 0; i <= x; i++)
		for (int j = 0; j <= y; j++)
			dp[i][j] = 0;


	for (int i = 1; i <= x; i++)
	{
		for (int j = 1; j <= y; j++)
		{
			if (str1[i - 1] == str2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}


	cout << dp[str1.length()][str2.length()];

	//for (int i = 0; i < x; i++)
	//{
	//	delete[] dp[y];
	//}

	//delete[] dp;

	return 0;
}

// VS에서 array의 index를 1000이상 선언하면 아예 돌아가지 않아서 동적할당을 사용하였는데 전역변수로 선언하면 그냥 돌아간다고 해서 코드 바꿨다 ㄱ-,,

#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;

const int bound = 1001;
int dp[bound][bound] = { 0 };

int main()
{
	string str1, str2;
	cin >> str1 >> str2;

	int x = str1.length();
	int y = str2.length();

	for (int i = 1; i <= x; i++)
	{
		for (int j = 1; j <= y; j++)
		{
			if (str1[i - 1] == str2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	cout << dp[x][y];

	return 0;
}

#1912

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int bound = 100000;
int arr[bound] = { 0 };
int dp[bound] = { 0 };

int main()
{
	int n;
	int result;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	dp[0] = arr[0];
	result = arr[0];

	for (int i = 1; i < n; i++)
	{
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
		result = max(result, dp[i]);
	}

	cout << result;

	return 0;
}

#12865

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int bound = 100001;
int dp[101][bound] = { 0 };
//dp 배열은 행은 전체 물건의 개수 index이고, 열은 무게를 1~K까지의 index이다.

int main()
{
	int N, K;
	int W[101] = { 0 };
	int V[101] = { 0 };
	int result = 0;
	cin >> N >> K;

	for (int i = 1; i <= N; i++)
	{
		cin >> W[i] >> V[i];
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= K; j++)
		{
			//물건을 넣을 수 있다면
			if (j >= W[i])
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			}
			else
			{
				//물건을 넣을 수 없다면
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	cout << dp[N][K];
	return 0;
}

//점화식 중 dp[i-1][j-W[i]] + V[i]가 이해가 잘 안갔는데
j가 1~K까지의 무게를 나타낸 것이므로 지금 무게에서 현재의 무게를 뺀 열로 가서 지금 행의 앞의 부분의 무게를 구하고 구한 무게에서의 가치와 현재의 가치를 더한 것과 앞에 있는 가치의 max를 비교해서 저장하는 것...