다이나믹 프로그래밍 문제 2

1. 가장 긴 증가하는 부분 수열(LIS)

문제 : https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

풀이

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

int main() {
	int n, max = 1;
	cin >> n;

	vector<int> d(n + 1, 1); 
	vector<int> a(n + 1, 0);

	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			// 현재 값보다 작고 새로운 수열을 만들 수 있을 경우
			if (a[i] > a[j] && d[i] <= d[j])
				d[i] = d[j] + 1;

			if (d[max] < d[i])
				max = i;
		}
	}


	cout << d[max];
}

2. 가장 긴 증가하는 부분수열 4(LIS)

문제 : https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

풀이

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

void print_v(int);
vector<int> v;
vector<int> a;

int main() {
	int n, max = 1;
	cin >> n;

	vector<int> d(n + 1, 1);
	v.assign(n + 1, 0);
	a.assign(n + 1, 0);

	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			// 현재 값보다 작고 새로운 수열을 만들 수 있을 경우
			if (a[i] > a[j] && d[i] <= d[j]) {
				d[i] = d[j] + 1;
				v[i] = j;
			}
			if (d[max] < d[i])
				max = i;
		}
	}
	cout << d[max] << endl;
	print_v(max);
}

void print_v(int idx) {
	if (idx == 0) 
		return;

	print_v(v[idx]);
	cout << a[idx] << " ";
}

3. 가장 긴 감소하는 부분수열(LDS)

문제 : https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

풀이

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

int main() {
	int n, max = 1;
	cin >> n;

	vector<int> d(n + 1, 1);
	vector<int> a(n + 1, 0);

	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			// 현재 값보다 크고 새로운 수열을 만들 수 있을 경우
			if (a[i] < a[j] && d[i] <= d[j])
				d[i] = d[j] + 1;

			if (d[max] < d[i])
				max = i;
		}
	}


	cout << d[max];
}

4. 가장 긴 바이토닉 수열

문제 : https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

풀이

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

int main() {
	int n, max = 1;
	cin >> n;

	vector<int> d(n + 1, 1);
	vector<int> d2(n + 1, 1);
	vector<int> a(n + 1, 0);

	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			// 증가 수열
			// 현재 값보다 작고 새로운 수열을 만들 수 있을 경우
			if (a[i] > a[j] && d[i] <= d[j])
				d[i] = d[j] + 1;
		}
	}
	for (int i = n-1; i >= 1; i--) {
		for (int j = n; j > i; j--) {
			// 뒤에서부터 증가 수열
			// 현재 값보다 작고 새로운 수열을 만들 수 있을 경우
			if (a[i] > a[j] && d2[i] <= d2[j])
				d2[i] = d2[j] + 1;
		}
	}

	// 최대 바이토닉 수열 찾기
	for (int i = 1; i <= n; i++)
		if (d[max] + d2[max] - 1 < d[i] + d2[i] - 1)
			max = i;

	cout << d[max] + d2[max] - 1;
}

5. 연속합

문제 : https://www.acmicpc.net/problem/1912

1912번: 연속합

풀이

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

int main() {
	int n, max=1;
	cin >> n;

	vector<int> d(n + 1);
	vector<int> a(n + 1);

	for (int i = 1; i <= n; i++)
		cin >> a[i];

	d[1] = a[1];
	for (int i = 2; i <= n; i++) {
		// 다시시작이 더 크면
		if (a[i] > a[i] + d[i - 1])
			d[i] = a[i];
		// 아니면
		else
			d[i] = d[i - 1] + a[i];

		if (d[max] < d[i])
			max = i;
	}

	cout << d[max];
}

6. 제곱수의 합

문제 : https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

풀이

#include <iostream>
#include <vector>
#define MAX 99999999
using namespace std;

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

	vector<int> d(n + 1, MAX);
	d[0] = 0, d[1] = 1; // 초기화
	// 2~n까지 DP
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j*j <= n; j++) {
			// 해당 값이 존재하고 더 작은 수로 만들 수 있으면
			if (i - (j*j) >= 0 && d[i - (j*j)] < d[i])
				d[i] = d[i - (j*j)] + 1;
		}
	}
	cout << d[n];
}