오늘의 문제
11055 가장 큰 증가하는 부분 수열
11053 가장 긴 증가하는 부분 수열
9461 파도반 수열
9084 동전
1915 가장 큰 정사각형

11055 가장 큰 증가하는 부분 수열

코드

#include <bits/stdc++.h>
using namespace std;

long long n, num[1002], dp[1002];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> num[i];
	dp[0] = num[0];
	
	long long ans = dp[0];
	for (int i = 1; i < n; i++) {
		for (int j = i - 1; j >= 0; j--) {
			if (num[j] < num[i]) {
				dp[i] = max(dp[i], dp[j] + num[i]);
			}
		}
		if (dp[i] == 0) dp[i] = num[i];
		ans = max(ans, dp[i]);
	}
	cout << ans;
}

항상 코너 케이스에 주의를,, 이 문제에서는 입력이 1개일 때를 주의해아한다.

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

코드

#include <bits/stdc++.h>
using namespace std;

int n, num[1002], dp[1002];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> num[i];
	int ans = 1;
	dp[0] = 1;

	for (int i = 1; i < n; i++) {
		for (int j = i - 1; j >= 0; j--) {
			if (num[j] < num[i]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		if (dp[i] == 0) dp[i] = 1;
		ans = max(ans, dp[i]);
	}
	cout << ans;
}

9461 파도반 수열

코드

#include <bits/stdc++.h>
using namespace std;

int t;
long long p[102];

int main() {
	cin >> t;
	p[1] = 1; p[2] = 1; p[3] = 1;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 4; i <= n; i++) {
			p[i] = p[i - 2] + p[i - 3];
		}
		cout << p[n] << "\n";
	}
}

9084 동전

코드

#include <bits/stdc++.h>
using namespace std;

int n, coin[20], m, dp[10002];

int main() {
	int t;
	cin >> t;
	while (t--) {
		fill(dp, dp + 10002, 0);
		cin >> n;

		for (int i = 0; i < n; i++) cin >> coin[i];
		cin >> m;
		dp[0] = 1;
		for (int i = 0; i < n; i++){
			for (int j = coin[i]; j <= m; j++) {
				dp[j] += dp[j - coin[i]];
			}
		}
		cout << dp[m] << "\n";
	}
}

1915 가장 큰 정사각형

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[1002][1002], dp[1002][1002];

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			arr[i][j] = c - '0';
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if(arr[i - 1][j - 1]) dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans * ans;
}

정말 어떻게 푸는건지 감을 못 잡았는데, dp 표를 직접 그려보았더니 조금 느낌이 왔다..