DOYLE DEVELOPMENT NODE

가장 긴 증가하는 부분 순열과 비슷하지만 약간의 트릭으로 스택에 수열을 넣고 다시 빼놓아서 뒤집어주고 동일한 방법으로 가장 긴 증가하는 부분 순열을 구하면 된다. 스택에 들어간 일련의 원소들은 순서가 뒤집어주는 성질이 있다. 유용하게 사용하자

가장 긴 증가하는 부분 수열 문제, 다이나믹 프로그램을 활용하면 된다. 힌트는 해당 수열의 부분이 이전 수들과 대소 비교를 해서 그 중 가장 길었던 수열에 +1 해주면 되는 것!

#include <iostream>
#include <algorithm>
using namespace std;
int d[1050];
int seq[1050];
int main()
{
	int input = 0;
	cin >> input;
	for (int i = 1; i <= input; ++i)
	{
		cin >> seq[i];
	}
	for (int i = 0; i <= input; ++i)
		d[i] = 1;
	for (int i = 2; i <= input; ++i)
	{
		for (int j = 1; j < i; ++j)
		{
			if (seq[i] > seq[i - j])
				d[i] = max(d[i], d[i - j] + 1);
		}
	}
	int ans = 0;
	for (int i = 1; i <= input; ++i)
		ans = max(ans, d[i]);
	cout << ans;
	return 0;
}

다이나믹 프로그래밍을 활용하는 문제. d[i][j] 가 i번째 포도주가 j번연속으로 와인을 먹은 상태이고 a[i]는 i번째에 든 포도주의 양이라고 하면

d[i][0] = max(d[i -1][0], d[i - 1][1], d[i - 1][2])

d[i][1] = d[i - 1][0] + a[i]

d[i][1] = d[i - 1][1] + a[i] 

로 점화식을 세울 수 있다. 0번 연속 마셨다면 이전의 포도주 중 가장 많은 값이 들어가야겠고 한 번이면 이전에(i - 1)에서 0번 연속 먹었을 때 두 번이면 한 번 연속 먹었을 때 일 것이다. 백준님께 들은 강의에서 내가 생각하는 경우로 코딩하면 대부분 틀린다고 항상 규칙을 찾고 일반적인 경우를 생각해야된다고 말씀하셨다.

#include <iostream>
#include <algorithm>
using namespace std;
long long d[10050][3];
long long wine[10050];
int main()
{
	int input = 0;
	cin >> input;
	for (int i = 1; i <= input; ++i)
	{
		cin >> wine[i];
	}
	d[0][0] = d[0][1] = d[0][2] = 0;
	//d[i][0] 연속해서 마신 포도주 0잔 ...
	for (int i = 1; i <= input; ++i)
	{
		d[i][0] = max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2]));
		d[i][1] = d[i - 1][0] + wine[i];
		d[i][2] = d[i - 1][1] + wine[i];
	}
	long long ans = 0;
	ans = max(d[input][0], max(d[input][1], d[input][2]));
	cout << ans;
	return 0;
}

다이나믹 프로그래밍을 이용하는 문제. 스티커를 뜯지 않았을 때, 위쪽을 뜯었을 때, 아래쪽을 뜯었을 때의 경우를 나누고 각 경우에 따라 이전의 스티커 상태와의 관계를 점화식으로 세운 후 코딩하면 된다. 마지막 출력에서 endl을 쓰지 않아서 답 찾느라고 고생했다.. 후 

이친 수 문제 1이 연속으로 나오지 않는 이진수를 말한다. 풀이는 상당히 쉽게 떠오르는데 다이나믹 프로그래밍을 사용하면 된다. 나는 강의를 듣고 있는지라 바로 다이나믹인 걸 알고 있으나.. 그렇지 않아도 충분히 떠오를만 하다. 일단 이친수의 자리 수를 n이라고 하면 끝이 0으로 끝나면 d[n]0]에 1로 끝나면 d[n][1]에 저장하면 d[n][i] += d[n -1][k] (k는 0일 때는 i가 0, 1 둘 다 더해주고 1일 때는 0 부분에만 더해주면 되겠다.) 같은 점화식으로 표현할 수 있다.

다이나믹 프로그래밍을 이용해서 푸는 문제 자리 수가 i이고 자리 수의 마지막 수가 j라고 하면 d[i][j] 라는 식으로 표현하고

이는 d[i][j] += d[i -1][k] (0 <= k<= j) 점화식으로 확장 될 수 있다. 잘 생각해보면 예를들어 마지막 수가 8이면 마지막 수가 0부터 8까지 전 자리 수의 개수를 더해주면 된다. 3중 for문이라 좀 당황했는데 n에 따라 변하지는 않으므로 복잡도는 O(n)이라고 볼 수 있을 것 같다.