급하게임개발

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

이 문제는 LIS 문제이다  그 이유는 이 문제의 경우 학생들을 원하는 위치이 넣을 수 있으므로 정렬되어 있지 않은 학생들을 정렬된 학생의 알맞은 위치에 넣으면 되는것이다 즉 전체 수에서 LIS만큼  뺴주면 되는 문제였다

#include <iostream>
#include <algorithm>
using namespace std;
int arr[200];
int dp[200] = { 0, };
int lis = 0;
int main() {
	int n,x,y;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <i; j++) {
			if (arr[i] > arr[j]) {
				dp[i]=max(dp[i], dp[j] + 1);
				lis = max(lis, dp[i]);
			}
		}
	}
	cout << n-lis;
}

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

이 문제는 내가 완전 감을 잘못 잡고 풀고 있었다. 이 문제를 증가수열 비슷하게 풀려고 했었다 하지만 이렇게 풀면 로직이 꼬였는데 테스트케이스 몇개는 잘나왔으나 몇개는 매우 잘 나오지 않았다.

이 문제의 로직은 현재 나를 기준으로 내왼쪽에서의 최대높이와 내오른 쪽의 최대높이를 비교해서 낮은 높이를 선택 해주는 문제 였다 단 오른쪽 과 왼쪽의 최대높이가 나보다는 클때만 빗물이 받아지니 해당 상황일때만 계산하도록 코드를 작성한다 그림으로 나타내면 대충 아래와 같다

해당 로직에 대한 코드는 아래 와 같다

#include <iostream>
#include<algorithm>
using namespace std;
int h, w;
int arr[500];
int main() {
	cin >> h >> w;
	int result = 0;
	for (int i = 0; i < w; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i < w - 1; i++) {
		int lmax = 0;
		int rmax = 0;
		for (int j = 0; j < i; j++) {
			if (lmax < arr[j] && arr[j]>arr[i])
				lmax = arr[j];
		}
		for (int j = i + 1; j < w; j++) {
			if (rmax < arr[j] && arr[j]>arr[i])
				rmax = arr[j];
		}
		if (lmax != 0 && rmax != 0)
			result += min(lmax, rmax) - arr[i];
	}
	cout << result;

}