급하게임개발

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

이건 개념은 쉬웠다 근데 계속 틀렸습니다 나오길 래 코드를 뜯어봤더니 int의 범위를 초과해서 갑자기 값이 음수로 바뀌는 사태가 발생해서 100정도를 넣으면 값이 이상하게 나왔다 그래서 이코드는 중간중간에 값에다가 모듈러 연산을 해서 저장해주는 게 해결책이었다.

자 일단 첫번째 자리수 즉 수의 맨앞에 나오는 수는 0이 나오면 안된다 그렇기에 첫번째 자릿수가 0

이 될 경우의 수 는 0이다 그리고 나머지는 첫번째 자리에 나오는게 가능하니 1이다

2번째자릿수의 0은 이전자리에서 1에서 오는 방법밖에 없다 9도 마찬가지다 9로가는 방법은

이전자리의 수에서 8에서 밖에 오는 방법밖에 없다

그래서 0일때의 점화식은

dp[i][j] = dp[i - 1][j + 1];

9일때의 점화식은

dp[i][j] = dp[i - 1][j - 1];

이렇게 된다

#include <iostream>
using namespace std;
long long dp[101][101];
int main() {
	long long N;
	long long sum = 0;
	cin >> N;
	dp[1][0] = 0;
	for (int i = 1; i <= 9; i++) {
		dp[1][i] = 1;
	}
	
	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j + 1];
			}
			else if (j == 9) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
				
			dp[i][j] = dp[i][j] % 1000000000;
		}

	}

	for (int i = 0; i <= 9; i++) {
		sum += dp[N][i];
		sum %= 1000000000;
	}
	cout << sum;
}

이 두 부분을 제외하고는 이전자리의 수에서 나보다 하나 크거나 하나 작은 곳에서 부터 올수 있으니

2개의 경우 의 수를 합쳐준다 즉

3번째 자리에 3은 2번째자리에 2와 4로부터 오는것이니 [2][4]+[2][2]를 하면 된다

그래서 이부분의 점화식은

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

이렇게 된다. 하지만 숫자가 너무 커지게 되니 이 연산이 끝나고 나면 모듈러 연산을 해주면 좋다

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

dp문제는 풀 때 마다 점화식이 중요하다고 생각되어진다 역시 이번 문제도 점화식인데

이번문제의 경우 기존에 올렸던과는 다르게 3개의 후보중 하나를 뽑는 방식으로 생각해주어야 한다

그이유는 이번 문제에서 핵심적인 내용이 연속으로 3개의 포도주를 못마신다는 거였으니  그거를 이용해서 풀어야 한다

1.O O X O

2.O X O O

3.X O O X

이문제는 위에처럼 3가지 경우의 수가 존재 한다 즉 N번째 와인이 존재한다고 가정했을때 N번째 와인을 마신다고 가정했을때 첫번째로 마시냐 두번째로 마시냐 혹은 안마시냐 이렇게 3개의 경우의 수가 존대 한다. 이를 점화식으로 나타내면

1은 dp[j-2]+arr[j];

2는 dp[j-3]+arr[j-1]+arr[j]

3은 dp[j-1]

이다 1은 j번째 포도주를 먹기로 가정했기 때문에 내이전은 못마시고 나보다 2개전에 있는 애를 마실 수 있다

2는 나도 마시고 내이전도 마신다고 가정한것이다 

마지막은 나를 안마셨기 때문에 나의 이전까지의 최대값만 필요하다 어차피 이렇게 우리가 3개의 식으로 나눴을 경우 3잔을 연속으로 마시는 경우의 수는 발생하지 않는다

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001];
int arr[10001];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];

	for (int j = 3; j <= n + 1; j++) {
		dp[j] = dp[j - 1];
		dp[j] = max(dp[j], dp[j - 2] + arr[j]);
		dp[j] = max(dp[j], dp[j - 3] + arr[j - 1] + arr[j]);

	}
	cout << dp[n] << endl;
}

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];
}