급하게임개발

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

얘는 살짝 만 생각하면 답이나오는 문제 였다. 문제 푸는 방법이 퍼뜩퍼뜩 났으면 좋겠는데 아직 수련이 부족해서 시간이 오래 걸린다.

이 문제는 간단하다 내이전에 나온 최댓값과 나를 더한값과 나 혼자 값중에 더큰애를 선택해주면 되는 문제였다.

그 이유는 어찌됬든 더하는 수가 양수라면 값은 증가하기 때문이다

10
10 -4 3 1 5 6 -35 12 21 -1

즉 이런식으로 입력이 주어지면

dp[1]은 -4와 6중에 선택한다

dp[2]는 3과 9중에 선택한다

dp[3]은 10과 1중에 선택한다

이런식으로 dp값이 바뀐다 즉 점화식은

max(dp[i-1]+arr[i],arr[i])값이 된다

#include <iostream>
using namespace std;
int arr[100000];
int dp[100000];
int max(int x,int y) {
	return x > y ? x:y;
}
int main() {
	int inputnum;
	int maxnum;
	cin >> inputnum;
	for (int i = 0; i < inputnum; i++) {
		cin >> arr[i];
	}
	dp[0]=arr[0];
	maxnum = dp[0];
	for (int i = 1; i < inputnum; i++) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
	}

	for (int i = 0; i < inputnum; i++) {
		if (dp[i] > maxnum) {
			maxnum = dp[i];
		}
	}
	cout << maxnum;
}

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

이 문제의 경우 여러가지 생각을 하게 해주었다 일단 처음에 visual studio 에서 

스택 사이즈를 너무 많이 먹는다고 경고를 띄우고 강제 종료되서 나를 개빡치게 했다

이건 지역변수가 스택에 할당 되서 문제였다

그래서 문제 해결법은 그냥 전역변수에 사이즈가 큰 배열을 갔다 박으면 되는 문제였다

또한 short로 하면 이문제는 틀렸습니다가 나온다 그이유는 각각의 수의 범위들은 short로

처리가 가능하지만 이 값들의 합은 short 범위 내에 있지 않을 가능성이 크기 때문이다

이에 변수들을 int로 정의 해주면 해결이었다

dp에 bottom up방식을 사용해서 풀었다.

나는 이문제가 이전에 풀었던 2 3짜리 문제 보다 훨씬 쉬었다

이문제의 경우 총 3개의 경우의 수를 생각해주어야한다

삼각형의 왼쪽끝과 오른쪽끝 그리고 이둘다 아닐경우가 다다르다

왼쪽끝과 오른쪽끝의 경우 자신의 부모가 하나밖에 없기 때문에 확정으로 값이 나온다

왼쪽은 이렇게 dp[j][k] = tri[j][k]+ dp[j - 1][k];

오른쪽은 이렇게 dp[j][k] = tri[j][k] + dp[j - 1][k-1];

둘다 아닌경우는 dp[j][k] = max((tri[j][k] + dp[j - 1][k]), (tri[j][k] + dp[j - 1][k - 1]));

이렇게 3개로 나누어줘야한다 아니면 불필요한 범위까지 계산하게 되서 백준에서 오류를 띄워준다.

#include <iostream>
using namespace std;
int tri[501][501];
int dp[501][501];

int max(int x, int y) {
	return x > y ? x : y;
}
int main() {
	int trisize;
	cin >> trisize;
	int maxnum = 0;

	for (int i = 0; i < trisize; i++) {
		for (int j = 0; j < i + 1; j++) {
			cin >> tri[i][j];
		}
	}
	dp[0][0] = tri[0][0];
	for (int j = 1; j < trisize; j++) {
		for (int k = 0; k <= j; k++) {
			if (k == 0) {
				dp[j][k] = tri[j][k]+ dp[j - 1][k];
			}
			else if (k == j) {
				dp[j][k] = tri[j][k] + dp[j - 1][k-1];
			}
			else {
				dp[j][k] = max((tri[j][k] + dp[j - 1][k]), (tri[j][k] + dp[j - 1][k - 1]));
			}
		}

	}
	for (int i = 0; i < trisize; i++) {
		if (dp[trisize-1][i] > maxnum) {
			maxnum = dp[trisize - 1][i];
		}
	}
	cout << maxnum;
}

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

처음 풀때 잘 못 생각했었다 순열안에 수를 뽑아 증가하는 수열을 만드는 거라 생각해서

처음 부터 다시 풀어야 했다

이번 꺼는 생각하는 게 좀 어려웠다 자기 자신의 이전의 경로의 수가 dp로 들어가야한다.

10 20 10 30 20 50

이렇게 수열이 있으면 처음 이렇게 만 있을 때 증가하는 수열들은 각각 하나 씩이라고 생각하자

그 후에 내 이전의 원소들을 보면서 비교한다 내 이전의 원소가 나보다 작으면

나의 수에 내 이전 원소 까지의 증가수를 합쳐준다 

예시로 

20이 10을 만나게 되면 10은 하나짜리 증가 수열이고 20은 10보다 크니

10 20은 증가수열이다 이에 서로까지의 증가 수열 수를 더해준다 이에 20은 

2의 증가 수열을 갖는다

하지만 이 때 내 이전 원소가 나보다 작을 수 있는 경우의 수가 여러 개이므로 

내 이전까지의 증가수열 수 + 1 끼리를 비교하여 가장 큰값을 내가 갖고 있어야 한다

이에 dp[i]=max(dp[i],dp[j]+1)  이 필요하다

이에 자기자신의 값과 내 이전의 증가수열이 나를 만났을 때의 개수 와 비교해 준다

이렇게 점점 자기자신보다 작은애까지의 증가수열 + 나의 값이 최대가 되는 것을 구하는게

핵심이다

#include <iostream>
using namespace std;
int max(int x, int y)
{
	return x > y ? x : y;
}
int main() {
	int arr[1001];
	int dp[1001]; //자신 까지의 증가 수열 수
	int maxnum=0;
	int inputn;
	cin >> inputn;
	for (int i = 0; i < inputn; i++) {
		cin >> arr[i];
		dp[i] = 1;
	}

	for (int i = 1; i < inputn; i++) {
		for (int j = 0; j <= i; j++) {
			if (arr[i] > arr[j]) {
				dp[i] = max(dp[i], dp[j]+1);
			}
		}
	}
	
	for (int i = 0; i < inputn; i++) {
		if (dp[i] > maxnum)
			maxnum = dp[i];
	}

	cout << maxnum;
}

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

백준 2579 번은 dynamic programming을 사용해서 풀어야 한다

dp를 하면서 느낀거는 점화식을 세우는 게 중요한거 같다.

일단 이 문제의 경우 기준은 마지막 계단이다.

마지막 계단을 올라가는 방법은 2가지가 있다

연속된 3계단을 올라갈 수 없으니 전계단과 전전전계단을 밟고 올라오는 경우의 수와

전전계단을 밟고 마지막 계단에 도착하는 경우의 수가 있다

이경우  점화식은 2개가 존재한다

이를 위해 i번째 계단까지 올라왔을 때의 최댓값을 저장해줄 dp 배열

각계단의 점수 값을 기록해줄 stair 배열을 생성해준다.

dp[i-3]+stair[i-1]+stair[i]

dp[i-2]+stair[i]

이렇게 2개가 있다

그리고 이점화식은 i가 3이상 일 때 부터 작동한다

이에 우리의 dp[0],dp[1],dp[2]는 반복문에 들어가기전에 미리 값을 삽입해 놓아야 한다.

#include <iostream>
using namespace std;
int max(int x, int y)
{
	return x > y ? x : y;
}
int main() {
	int inputn = 0;
	int stair[301] = { 0, };
	int dp[301] = { 0, };
	cin >> inputn;
	for (int i = 0; i < inputn; i++) {
		cin >> stair[i];
	}
	dp[0] = stair[0];
	dp[1] = max(stair[1] + dp[0],stair[1]);
	dp[2] = max(stair[2]+stair[1], dp[0]+stair[2]);

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